关于怎么判断一个数 n 是否是质数，最简单的方法是枚举 2 到 n−1，判断是否是 n 的约数。如果是， n 肯定不是一个质数。再仔细想想，如果 a 是 n 的一个约数，那么必然有一个b 满足 ab = n，a≤√n 和 b≤√n 中必然有一个成立，因为如果a>√n 并且 b>√n，那么 ab>n，和 ab = n 矛盾。因此如果 n 是一个合数，那么我们只需要枚举到 √n 就一定能找到 n的一个约数。否则，n 肯定是一个质数。下面是代码：
int is_prime(int n)
{
for(int i = 2; i * i <= m; i++)
if(n % i == 0)
return 0;//不是质数
return 1;//是质数
}
更多的时候，需要预处理出一段区间上的质数，如果按照之前的方法一个一个判断，时间上肯定会承受不了。于是提出了一种预处理 1 到 N 上质数的算法，称为 Eratosthenes 筛选。
素数筛选算法的基本思想是我们先假设 2 到 N 所有数都是素数。我们从 2 开始扫描，对于一个数 i，可以得到 2i, 3i ……ki 都不是素数，因为这些数都有 i 这个因子，表示这些数不是素数，一直枚举到 N。对于每一个合数，它至少会被它的一个因子枚举到，所以可能证明这个算法的正确性。接下来分析时间复杂度，对于每个 i，枚举的次数为 n / i，所以总时间复杂度为 N/2 + N/3 + … + N/N = O(NlgN) 。
下面是代码:
for(int i = 2; i <= n; i++)
{
is_prime[i] = 1;
}
for(int i = 2; i <= n; i++)
{
for(int j = i * 2; j <= n; j += i)
{
is_prime[j] = 0;
}
}
上面的代码便筛选出来了 n 以内的素数，如果 is_prime[i] = 1，i 是素数，否则 i 是合数。上面的代码还可以优化。第一是基于每个合数必然有一个质因子，所以我们可以只用质数来筛选，第二是 j 的初始条件可以写成 j = i * i，因为比如 j = i * k( k < i), 那么 j 肯定被k 筛选掉了。第三是可以只用√n 之前的质数去筛选。优化之后的时间复杂度比O(NlgN)还要低得多。优化以后的代码如下：
for(int i = 2; i <= n; i++)
{
is_prime[i] = 1;
}
for(int i = 2; i * i <= n; i++)
{
if(is_prime[i])
{
for(int j = i * i; j <= n; j += i)
{
is_prime[j] = 0;
}
}
}
