K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
要判定n是否为质数，必须遍历2到n-1的所有整数检查是否能整除n，否则无法准确判定。
可以将遍历范围优化为2到√n，且提前排除所有大于2的偶数，能在不影响准确率的前提下提升判定效率。
如果n除以2余数不为0，那么n一定是质数。
质数判定算法的时间复杂度最优为O(n)，无法进一步优化。