素数线性筛模板

╰+哭是因爲堅強的太久メ 2022-05-14 03:36 238阅读 0赞

[参考于该博客][Link 1]

int Mark[MAXSIZE];  
    int prime[MAXSIZE];  
      
    //判断是否是一个素数  Mark 标记数组 index 素数个数  
    int Prime(){  
        int index = 0;  
        memset(Mark,0,sizeof(Mark));  
        for(int i = 2; i < MAXSIZE; i++)  
        {  
            //如果未标记则得到一个素数  
            if(Mark[i] == 0){  
                prime[index++] = i;  
            }  
            //标记目前得到的素数的i倍为非素数  
            for(int j = 0; j < index && prime[j] * i < MAXSIZE; j++)  
            {  
                Mark[i * prime[j]] = 1;  
                if(i % prime[j] == 0){  
                    break;  
                }  
            }  
        }  
        return index;  
    }

利用了每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。  
代码中体现在：  
if(i%prime\[j\]==0)break;  
prime数组 中的素数是递增的,当 i 能整除 prime\[j\]，那么 i\*prime\[j+1\] 这个合数肯定被 prime\[j\] 乘以某个数筛掉。  
因为i中含有prime\[j\], prime\[j\] 比 prime\[j+1\] 小。接下去的素数同理。所以不用筛下去了。  
在满足i%prme\[j\]==0这个条件之前以及第一次满足改条件时,pr\[j\]必定是pr\[j\]\*i的最小因子

[Link 1]: https://blog.csdn.net/dl962454/article/details/76595623

发表评论取消回复

表情：

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

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

相关阅读

相关 P3383 【模板】线性筛素数---洛谷

题目描述题目背景本题已更新，从判断素数改为了查询第 k 小的素数提示：如果你使用 cin 来读入，建议使用 std::ios::sync\_with\_st

雨点打透心脏的1/2处/ 2023年07月18日 06:54/ 0 赞/ 9 阅读

相关 ACM.素数筛

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

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

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 145 阅读

相关素数筛模板

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

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

相关一般筛法和快速线性筛法求素数求素数的一点总结

素数总是一个比较常涉及到的内容，掌握求素数的方法是一项基本功。基本原则就是题目如果只需要判断少量数字是否为素数，直接枚举因子2 。。N^(0.5) ，看看能否整除N。如

待我称王封你为后i/ 2022年08月09日 12:54/ 0 赞/ 186 阅读

相关素数基本（埃氏筛法/线性筛法）

一、检查n是否为素数最简单思路：所有可能的因数全部试一遍。 int gg(int n) { for(int i=2;i<n;i

拼搏现实的明天。/ 2022年05月17日 06:10/ 0 赞/ 267 阅读

相关素数线性筛模板

[参考于该博客][Link 1] int Mark[MAXSIZE]; int prime[MAXSIZE]; //判断是

╰+哭是因爲堅強的太久メ/ 2022年05月14日 03:36/ 0 赞/ 239 阅读

相关素数筛法

//暴力枚举素数筛法 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 阅读

相关 [模板] 积性函数 && 线性筛

积性函数数论函数指的是定义在正整数集上的实或复函数. 积性函数指的是当 \\((a,b)=1\\) 时, 满足 \\(f(a\b)=f(a)\f(b)\\) 的数论

左手的ㄟ右手/ 2022年01月08日 00:43/ 0 赞/ 216 阅读