数论2：素数筛

向右看齐 2021-09-20 11:56 386阅读 0赞

## 埃氏筛 ##

判断素数可通过试除小于\\(\\sqrt n\\)的素数来实现，那么将其反过来，只要将\\(<= \\sqrt n\\)的素数的倍数都删掉，那么就能得到一张\\(<=n\\)的素数表，\\(O(n\\lg \\lg n)\\)

// 需划掉合数，所以最初假设均为素数，即数组初始化为0
    bool composite[maxn];
    
    void generate(int n)
    {
        for(int i = 2, lim = sqrt(n); i <= lim; ++i) {
            if(composite[i]) continue;
            for(int j = i*i; j <= n; j += i)
                composite[j] = 1;
        }
        for(int i = 2; i < n; ++i)
            if(!composite[i]) printf("%d ", i);
        putchar('\n');
    }

## 线性筛 ##

埃氏筛的问题在于一个合数可能会被多个素数删除，造成不必要操作。为解决该问题，注意到每个合数均可写成其最小素因数p乘C，即\\(n=pC\\)，其中必有\\(C \\ge p\\)，因为若非如此，当C为素数时，不满足假设“p为最小素因数”；当C为合数时，其必能分解除小于C的素因数，同样不满足假设“p为最小素因数”。线性筛就是通过从小到大地遍历C来保证每个合数均被，其仅被删除一次。

// composite同样初始化为0；np是素数个数；prime保存找到的素数
    bool composite[maxn];
    int np, prime[maxn];
    
    void generate2(int n)
    {
        // 这里的i就是上述讨论中的C
        for(int i = 2; i <= n; ++i) {
            if(!composite[i]) prime[np++] = i;
            for(int j = 0; j<np && i*prime[j]<=n; ++j) {
                composite[i*prime[j]] = 1;
                // 为什么在这里break，类比完全背包思考一下 (^_^)
                if(i % prime[j] == 0) break;
            }
        }
        for(int i = 0; i < np; ++i)
            printf("%d ", prime[i]);
        putchar('\n');
    }

转载于:https://www.cnblogs.com/sequix/p/8524770.html