下面这两个的算法求N=1000000 内的质数 速度差不多，第一个要快点：
复杂度O(sqrt(N)*longlong(N))
# include <stdio.h> # include <math.h> # define N 1000000 char A[N]; int B[N/10]; //# define AA(i,j,A,Q) for(A[0]=A[1]=1,Q=sqrt(Q),i=2;i<Q;i++)if(!A[i])for(j=i<<1;j<N;j+=i)A[j]=1; int main(){ int i,num; num=ZHISHU(A,B,N); printf("%d ",num); for(i=0;i<num;i++) printf("%d ",B[i]); return 0; } int ZHISHU(char S[],int T[],int M) { int i,j,k=0,Q=sqrt(M)+1; for(S[0]=S[1]=1,i=2;i<Q;i++) if(!S[i]) { for(j=i<<1;j<M;j+=i) S[j]=1; T[k++]=i; } do{ if(!S[i])T[k++]=i; }while(++i<M); return k; } 第二个： # include <stdio.h> # define MAX 1000000 int prime[MAX/10]; char A[MAX]; void getPrime() { int i,j; for(i=2;i<MAX;i++) { if(!A[i])prime[++prime[0]]=i; for(j=1;j<=prime[0]&&prime[j]<=MAX/i;j++) { A[prime[j]*i]=1; if(!(i%prime[j])) break; } } } int main(){ int i; getPrime(); for(i=0;prime[i];i++) printf("%d ",prime[i]); return 0; } 还有就是平时用到的： # include <stdio.h> # include <math.h> # define N 1000000 char S[N]; # define AA(i,j,A,Q) for(A[0]=A[1]=1,Q=sqrt(Q),i=2;i<Q;i++)if(!A[i])for(j=i<<1;j<N;j+=i)A[j]=1; int main() { int i,j,Q=N; AA(i,j,S,Q);//经过筛法后 如果i是质数则S[i]=0 否则为1 for(i=0;i<N;i++) if(!S[i])printf("%d ",i); return 0; } 二：大数区间内素数的个数:给定整数A B 求[A,B)内有多少素数 条件A B∈[1,10^12] B-A<=10^7 EG: A=22801763489 B=22801787297 输出:1000 Time limite <=5S 解:当数很大的时候EG 10^12时 如果用sqrt()欧拉法或者埃氏筛法 也会很慢 因此 这两种方法 需要做结合 首先 区间(A,B)指的是所有满足A<=X<=B的整数所构成的集合 B以内的最小因数不会超过[sqrt(B)] 如果有sqrt(B)以内的素数表的话 就可以把埃氏筛法运用到[A,B)上了 即：先做好[2,sqrt(B))的表和[A,B)的表，然后从[2,sqrt(B))表中筛选出素数的同时 也将其倍数从[A,B)的表中划去 最后剩下的就为[A,B)的素数了
/*区间内素数的个数 给定整数A B 求[A,B)内有多少素数 条件A B∈[1,10^12] B-A<=10^7 EG: A=22801763489 B=22801787297 输出:1000 Time limite <=5S 解:当数很大的时候EG 10^12时 如果用sqrt()欧拉法或者埃氏筛法 也会很慢 因此 这两种方法 需要做结合 首先 区间(A,B)指的是所有满足A<=X<=B的整数所构成的集合 B以内的最小因数不会超过[sqrt(B)] 如果有sqrt(B)以内的素数表的话 就可以把埃氏筛法运用到[A,B)上了 即：先做好[2,sqrt(B))的表和[A,B)的表，然后从[2,sqrt(B))表中筛选出素数的同时 也将其倍数从[A,B)的表中划去 最后剩下的就为[A,B)的素数了 代码 C语言 # include <stdio.h> # include <math.h> typedef long long LL;//有些编译器 为 long long const long long MAX=1000000000000LL; # define N 10000001 # define max(a,b) ((a)>(b)?(a):(b)) char TT[N]={"\0"},Flag[N]={"\0"};//用char代替LL 节省空间 全部初始化为0 LL gainLL(LL *p,LL a,LL b); LL SUN(LL A,LL B); LL main(){ LL A,B; gainLL(&A,2,MAX); gainLL(&B,A+1,A+N); printf("%lld\n",SUN(A,B)); return 0; } LL SUN(LL A,LL B){ LL i,C=B-A,j,sum=0,D=(LL)sqrt(B++)+1; for(i=2;i<D;i++) if(!Flag[i]) { for(j=i<<1;j<D;j+=i)//筛选[2,sqrt(b)] Flag[i]=1; for(j=i*max(2,(A+i-1)/i);j<B;j+=i)//筛选[A,B) TT[j-A]=1; } for(i=0;i<C;i++) //统计质数的个数 若求(a,b)只要把i=0改为i=1 sum+=!TT[i]; return sum; } LL gainLL(LL *p,LL a,LL b)//输入LL *p直至满足(a,b)输入结束 { do{ *p=a-1; scanf("%lld",p); while(getchar()!='\n'); if(*p>b||*p<a) printf("输入有误,请重新输入\n%lld--%lld:\n",a,b); }while(*p>b||*p<a); return *p; } 蓝桥杯今年B组第二题 求长度为10的最小公差素数列的公差 # include <stdio.h> # define N 10000 //本题目N取10000就行 不过为了准确 还是最好取得大点 1000000 # define Max 10 //求长度为Max的等差素数列 char A[N]={"\0"};//1--- N的素数 N可>=1000000000 int main(){ int i,j,k,m; for(i=0;i<N;i++) A[i]=1; for(i=2;i<N;i++) if(A[i]) for(j=i+i;j<N;j+=i) A[j]=0; //用埃氏筛法求得素数 A[2] A[3] A[5]……都是素数 for(m=1;m<N;m++)//m为公差 for(i=2;i<N;i++)//i用来检测谁是素数 if(A[i]) { for(j=i,k=0;j<N;j+=m) if(A[j]&&k<Max)//比较后序的是否为素数 k++; else if(k==Max) { printf("%d\n",m); getchar(); } else break; //如果都不满足 则i向下走 } return 0; }