[除余法]求一亿以内的质数

优化一

最原始的除余法就是对于 $ k \in \lbrack 2,n \rbrack $ 把 $ \lbrack 2,k \rbrack $ 都试一遍，但这种效率显然非常低下，几乎大家都知道集合可以缩小为 $ \lbrack 2,\sqrt{k} \rbrack $，那么可以得到如下代码：

for (i = 3; i <= n; i++) {
    for (j = 2; (j * j <= i) && (i % j); j++) // 遍历到 sqrt(i) 或者可以整除
        ;
    if (i % j) // 不能整除，说明遍历到了 sqrt(i)，是质数
        prime[total++] = i;
}

优化二

上述的优化只是最基础的，我们进一步思考，所有偶数（除了 2）都是合数，那么我们其实可以直接把偶数排除在外，也就是循环的步长变成 2，这样可以直接筛去一半的数，效率提升一倍左右。其实这个思路是可以一直优化下去的，比如筛去 3 的倍数、5 的倍数，但太多就没必要了，因为计算步长会变得非常复杂。

个人觉得筛去 2 和 3 是最好的。将所有数分成 6 个一组，那么其中只剩下了 $ 6n+1 $ 和 $ 6n+5 $，步长是 $ 2, 4, 2, 4, ... $，计算起来也比较方便，同时能筛去 $ \frac{2}{3} $ 的数字，代码如下：

int k = 2;
for (i = 7; i <= n; i += (k ^= 6)) { // 从 7 开始，因为 7 = 6 * 1 + 1，同时 k 的初始值为 2 而非 4
    for (j = 2; (j * j <= i) && (i % j); j++)
        ;
    if (i % j)
        prime[total++] = i;
}

优化三

第二个优化思路已经到底了，再多程序就会变得复杂，效率的提升也不高，不划算，这里再给出第三种思路。

我们可以发现，在第二重循环中，如果 i 可以整除 j，同时 j 是个合数的话，那么在之前就应该已经被 j 的因数整除了，所以对于合数 j，我们可以直接跳过，也就是说 j 只需要是质数就可以，由于我们找到一个质数就将它存入 prime 数组，所以完全可以将 prime 利用起来，代码如下：

int g = 2
for (i = 7; i <= n; i += (g ^= 6)) {
    for (j = 0; (prime[j] * prime[j] <= i) && (i % prime[j]); j++)
        ;
    if (i % p[j])
        prime[(*total)++] = i;
}

因为合数远远多于质数，所以这里的效率提升是非常大的，只不过具体有多少不好计算，毕竟没有一个可以计算 $ n $ 以内质数个数的公式（如果有，那么只需要给 $ f(n) $ 和 $ f(n-1) $ 做个差就知道 $ n $ 是不是质数了，没必要用除余法）。

项目开源链接

密码生成器：https://github.com/WilfredShen/PasswordGenerator

求质数的代码在里面找得到

个人博客：https://wilfredshen.cn/

[除余法]求一亿以内的质数

原文：https://www.cnblogs.com/wilfredshen/p/13278329.html