素数

素数@(算法)素数简介质数（prime number）又称素数。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。还能被其他数（0除外）整除的数为合数。判断一个数是否是素数根据定义，除了1和本身之外没有其他约束，所以判断是否为质数，根据定义直接判断从2到n-1是否存在n的约数。方法一：暴力破解！bool isPrime(int num){ for(int i=2;i<num;i++){ if(num%i ==0){ return 0; } } return 1;}上述方法，明显存在效率极低的问题。一个数若可以进行因式分解，那么分解时得到的两个数，一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)改进：bool isPrime(int num){ int t=sqrt(num); for(int i=2;i<num;i++){ if(num%i ==0){ return 0; } } return 1;}方法二：素数筛法可以提前处理出来1n 的全体素数1.把1n列出来2.去掉不是特殊的13.从小到大，枚举每一个没有删掉的数字i把 i 的2倍，3倍，4倍，…,删掉剩下的没被删掉的都是素数const int N=100;int notprime[N];int main(){ notprime[1]=1; for(int i=2;i<N;i++){ if(notprime[i]==0){ for(int j=i+i;j<N;j=j+i){ ////删掉2i,3i,4*i…… notprime[j]=1; } } } for(int i=1;i<N;i++){ if(notprime[i]!=1){ printf("%d\t",i); } } return 0;}方法三：欧拉筛法在素数筛法中，有很多合数被删除多次。而欧拉筛法提供两个数组，一个是素数表，另一个是删除合数表(值为1表示表示不是素数)。const int N=100;int notprime[N]; //删除标记,值为1表示表示不是素数int prime[N]; //素数表int main(){ int t=0; //初始化素数表为空 notprime[1]=1; for(int i=2;i<N;i++){ if(notprime[i]==0){ //找到一个没有被删除的数 prime[t++]=i; //加入素数表 } for(int j=0;j<t&&prime[j]*i<N;j++){ //枚举素数表 notprime[prime[j]*i]=1; if(i%prime[j]==0){ break; //保证了每个合数只会被它的最小素因子筛掉 } } } for(int i=0;i<N;i++){ if(prime[i]!=0){ printf("%d\t",prime[i]); } }}prime[]数组中的素数是递增的,当i能整除prime[j]，那么 prime[j]*i 这个合数肯定被prime[j]乘以某个数筛掉。i%prime[j]==0保证了每个合数只会被它的最小素因子筛掉。参考[1]http://www.cnblogs.com/zhuoha…[2]http://www.cnblogs.com/zhuoha…[3]https://baike.baidu.com/item/…