筛法判断素数

ゝ一纸荒年。 2021-06-22 15:37 394阅读 0赞

1.埃氏筛选法

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn=1e6+10;

int n,num;
    int ans[maxn];//ans数组用来存放质数
    bool p[maxn];//p[i], i为质数则为false否则为true

void find_prime(int n){ 
    	for(int i=2;i<=n;i++){ 
    		if(p[i]==false){ 
    			 ans[num++]=i;
    			 //用质数筛掉他所有的倍数 
    			for(int j=i+i;j<=n;j+=i){ 
    			//如果一个数是质数，那么该质数的倍数一定不是质数 
    				p[j]=true;
    			}
    		}
    	}
    }

int main(){ 
     cin>>n;
     find_prime(n);
     cout<<num;
    	return 0;
    }

2.线性筛

线性筛的核心就是每次晒的时候保证是用在小质因子筛去的
    线性筛法-O(n), n = 1e7的时候基本就比埃式筛法快一倍了
    当n比较小的时候两种筛法速度差不多

#include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn=1e6+10;

int n,num;
    int ans[maxn];//ans数组用来存放质数
    bool p[maxn];//p[i], i为质数则为false否则为true

void find_prime(int n){ 
    	for(int i=2;i<=n;i++){ 
    		if(p[i]==false){ 
    			 ans[num++]=i;
    		}
    		for(int j=0;j<num&&ans[j]<=n/i;j++){ 
    			 //对于任意一个合数x，假设pj为x最小质因子，当i==x/pj时，一定会被筛掉
    			 p[ans[j]*i]=true;
    			 if(i%ans[j]==0){ 
    			 	break;
    		//1.i%pj == 0,因为pj是从小到大枚举的 pj定为i最小质因子，pj也定为pj*i最小质因子
    		//2.i%pj != 0, pj定小于i的所有质因子，所以pj也为pj*i最小质因子
    			 }
    		}
    	}
    }

int main(){ 
     cin>>n;
     find_prime(n);
     cout<<num;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关素数筛法略

用筛法求素数的基本原理，是把从1开始的某一范围内的正整数从小到大顺序排列，逐步筛掉非素数留下素数。用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列

墨蓝/ 2022年10月25日 01:23/ 0 赞/ 124 阅读

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

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

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

相关 5.2 筛法求素数

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

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

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

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

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

相关筛法求素数

用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时

我不是女神ヾ/ 2022年05月12日 14:42/ 0 赞/ 208 阅读

相关素数筛法

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

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

相关素数筛C++

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

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

相关埃拉托色尼筛法（素数筛）

列举大于等于2的整数，将其倍数划掉，往后遍历发现被划掉的直接略过，还没被划掉的则是质数（表示其不是前面任何一个数的倍数，也即没有除1和本身外的因子）。时间复杂度 O(Nlogl

骑猪看日落/ 2021年07月16日 21:52/ 0 赞/ 366 阅读

相关筛法判断素数

1.埃氏筛选法 include <iostream> include <algorithm> using namespace std; con

ゝ一纸荒年。/ 2021年06月22日 15:37/ 0 赞/ 395 阅读