筛选质数
题目:
输入一个正整数n,0<n,让n小于
吧,判断n是否是质数
方法一:试除法(最简单)
分析:
用for(int i=2;;)来从2到n遍历,如果n能被i整除,就不是质数。
代码:
bool zhi_1(int n) { if(n==1) return 0; for(int i=2;i<n;i++) { if(x%i==0) return 0; } return 1; }
优化:
因为因子都是成对出现,比如24,可以分成2 12,3 8,4 6;但我们只要判断它有没有较小的那个因数,如果没有,后面就不必判断。所以我们可以只让i<sqrt(n)。
代码:
bool zhi_2(int n) { if(n==1) return 0; else if(n==2) return 1; else { int b=sqrt(x); for(int i=2;i<=b;i++) { if(x%i==0) return 0; } return 1; } }
总结:
时间复杂度是
级别的,数据范围大时很不好用,但是思路简单。
方法二:6倍原理
分析:
对于所有的素数(除了2,3以外),都只有在6的倍数的左右两边有可能出现。一般要是数太大,导致要开很大的数组,就不用欧拉筛,总之就是在空间和时间之间抉择。
6倍原理的好处是可以判断一个数是否是质数,而欧拉筛是得出来的一组质数,要是判断单个数,用6倍原理。
代码:
bool zhi_3(int x)//目前已知最快的方法,相对方法2,节约三分之二时间,应该用这个就很少会超时吧。。 { if(x==1) return 0; else if(x==2||x==3)//如果是2,3直接是素数 return 1; if(x%6!=1&&x%6!=5)//如果不是6的倍数左右两边的数,就不是质数 return 0; int b=sqrt(x); for(int i=5;i<=b;i+=6)//判断x能否被小于根号n的,在6的倍数两边的数整除 { if(x%i==0||x%(i+2)==0)//能被整除就不是质数 return 0; } return 1; }
结论:
比前一个方法要判断的数据少了三分之二,但也不是最快的。
方法三:埃氏筛法
分析:
埃拉托斯特尼 (Eratosthenes) 筛法,简称埃氏筛或爱氏筛,为了得到自然数 n 以内的全部素数,必须把不大于根号 n 的所有素数的倍数剔除,剩下的就是素数。给出要筛数值的范围 n,先用 2 去筛,即把 2 留下,把 2 的倍数剔 除掉;再用下一个质数,也就是 3 筛,把 3 留下,把 3 的倍数剔 除掉;接下去用下一个质数 5 筛,把 5 留下,把 5 的倍数剔除 掉;不断重复下去...
代码:
#include<iostream> using namespace std; const int N=1e9;//一般大于输入的n的上限 int n,sum=0,zhi[N];//sum记录质数的个数,zhi[]数组用来依次记录质数。 bool status[N];//记录每个数的状态,1代表不是质数,0代表是质数,刚开始都是0; void pan(int n) { status[1]=1; for(int i=2;i<=n;i++)//从2到n遍历 { if(status[i]==0)//如果这个数字i是质数 zhi[sum++]=i;//记录下来这个质数。 for(int j=i*2;j<=n;j+=i) status[j]=1;//将质数的倍数记录为1,即不是质数。 } } int main() { scanf("%d",&n); pan(n); return 0; }
优化:
因为偶数里面只有2是素数,所以我们可以只去将质数的倍数排除掉就行。,即将里面的for循环拉到if语句里。
代码:
#include<iostream> using namespace std; const int N=1e9;//一般大于输入的n的上限 int n,sum=0,zhi[N];//sum记录质数的个数,zhi[]数组用来依次记录质数。 bool status[N];//记录每个数的状态,1代表不是质数,0代表是质数,刚开始都是0; void pan(int n) { status[1]=1; for(int i=2;i<=n;i++)//从2到n遍历 { if(status[i]==0)//如果这个数字i是质数 { zhi[sum++]=i;//记录下来这个质数。 for(int j=i*2;j<=n;j+=i) status[j]=1;//将质数的倍数记录为1,即不是质数。 } } } int main() { scanf("%d",&n); pan(n); return 0; }
总结:
复杂度为nloglogn,应该仅次与欧拉筛法。这个筛数的思路也很好。
方法四:欧拉法/线性筛数法(我已知的里,最快的)
分析:
在埃氏筛法中,对于6这个数,我们发现它被2,3,都枚举了一次,这样造成了时间的浪费,欧拉筛就在此进行改进。让每个合数只被它的最小质因子筛选一次 。
代码:
#include<iostream> using namespace std; const int N=1e9;//一般大于输入的n的上限 int n,sum=0,zhi[N];//sum记录质数的个数,zhi[]数组用来依次记录质数。 bool status[N];//记录每个数的状态,1代表不是质数,0代表是质数,刚开始都是0; void pan(int n) { for(int i=2;i<=n;i++) { if(states[i]==0) zhi[sum++]=i;//记录质数 for(int j=0;i*zhi[j]<n;j++) { status[zhi[j]*i]=1; if(i%zhi[j]==0)//zhi[j]就是i的最小质因子,跳出循环 break; } } } int main() { scanf("%d",&n); pan(n); return 0;
总结:
时间复杂度最小的算法,为O(n)。