数论2：素数筛

向右看齐 2021-09-20 11:56 373阅读 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

发表评论取消回复

表情：

评论列表（有 0 条评论，373人围观）

还没有评论，来说两句吧...

相关阅读

相关 ACM.素数筛

一.埃氏筛筛法的思想是去除要求范围内所有的合数，剩下的就是素数了，而任何合数都可以表示为素数的乘积，因此如果已知一个数为素数，则它的倍数都为合数。合数的倍数一定会在

清疚/ 2023年07月05日 11:57/ 0 赞/ 5 阅读

相关 POJ 2689【筛法求素数+区间筛素数】

Discription The branch of mathematics called number theory is about properties of numb

桃扇骨/ 2023年07月04日 06:15/ 0 赞/ 22 阅读

相关数论-素数

文章目录判断素数筛法求素数例题 HDU-1262 HDU-3792 判断素数 -----------------

女爷i/ 2022年11月27日 12:22/ 0 赞/ 228 阅读

相关素数筛模板

查找N内所有素数 1.埃氏筛 include<iostream> using namespace std; typede

约定不等于承诺〃/ 2022年11月06日 00:59/ 0 赞/ 162 阅读

相关 5.2 筛法求素数

![70][]![70 1][]![70 2][]![70 3][] 一个数，如果只有1和它本身两个[因数][Link 1]，这样的数叫质数（或素数）。如2、3、5、7都是质

今天药忘吃喽~/ 2022年05月20日 07:18/ 0 赞/ 214 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 260 阅读

相关素数筛C++

埃拉托斯特尼筛法（sieve of Eratosthenes ）是古希腊数学家埃拉托斯特尼发明的计算素数的方法。对于求解不大于n的所有素数，我们先找出sqrt(n)内的所有素

向右看齐/ 2022年02月09日 11:15/ 0 赞/ 280 阅读

相关数论——质数筛法

一、埃拉托斯特尼（Eratosthenes）筛法算法思想：　　要得到自然数n以内的全部素数，必须把不大于![5ab5c9ea15ce36d3884f4f0b39f33a

小灰灰/ 2021年11月10日 02:04/ 0 赞/ 451 阅读

相关数论——素数

转自：[http://www.cnblogs.com/linyujun/p/5198832.html][http_www.cnblogs.com_linyujun_p_5198

向右看齐/ 2021年11月01日 06:16/ 0 赞/ 397 阅读

相关数论2：素数筛

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

向右看齐/ 2021年09月20日 11:56/ 0 赞/ 374 阅读