一起来求素数
题目要求:打印出1-20亿之间的所有素数 C言语实现。如果动态申请内存就要考虑你机子的内存是不是够了。
当然在内存允许的情况下越快越好 真不希望看个黑屏看半小时。。。
给代码 大家一起来测速(能运行就只比速度) 前三名给分 60 30 10 呵呵。
#include <stdio.h> #include <time.h> #define MAX 2000000000 #define N MAX/32+1 unsigned int A[N]; int main() { clock_t start,finish; start=clock(); int i,k,n=N,max=MAX,size=sqrt(max),x,y; memset(A,0,sizeof(A)); for (i=2; i<size; i++) if (!(A[(i-1)/32]&(1<<((i-1)%32)))) { k=i+i; while (k<=max) { A[(k-1)/32]|=(1<<((k-1)%32)); k+=i; } } FILE *f=fopen("prime.txt","w"); for (i=2; i<=max; i++) if (!(A[(i-1)/32]&(1<<((i-1)%32)))) fprintf(f,"%d\n",i); fclose(f); finish=clock(); printf("%.3lf\n",((double)finish-start)/1000); system("pause"); }
// 准筛法求一万亿以内素数(VC 6.0) // 耗时13137.3秒(Dell机) #include <stdio.h> #include <time.h> //用于统计时间的头文件 #include <stdlib.h> #include <memory.h> #define PMAX 2000000000 //原著这里是100亿 我给改成20亿了 100亿要耗时好几个小时呢 #define NUMP 78500 long prime [NUMP]={2, 3}; long prime2[NUMP]={4, 6}; void set_Prime_table(void) { long n=5,p2=9, k,kr=1,kp=2; while(1) { if(n==p2) { kr++; p2=prime[kr]*prime[kr]; continue; } for(k=1; k<kr; k++) { if(n % prime[k]==0)goto nadd2; } prime[kp]=n; prime2[kp]=n+n; if(++kp==NUMP)break; nadd2: n=n+2; } if((__int64)n*n<PMAX)abort( ); return; } int main(void) { #define BLOCK 0x8000 //VC6.0最佳值(Dell机), 在赛扬-333上0x4000为最佳 static char pp[BLOCK]; __int64 BASE,np=0; long block,dn,k,nn,t2,t1=clock( ); //t1、t2分别记录开始和结束时间 set_Prime_table( ); for(np=BASE=0;BASE<PMAX;BASE+=BLOCK) { memset(pp,1,BLOCK); //预设都是素数 if(BASE==0)pp[0]=pp[1]=0; //0和1不是素数 block = BLOCK; if(PMAX-BASE<BLOCK)block=(long)(PMAX-BASE); for(k=0; k<NUMP; k++) { dn = prime [k]; nn = prime2[k]; while(nn<block) { pp[nn]=0; nn=nn+dn; } prime2[k]=nn-BLOCK; } for(k=0; k<block; k++)if(pp[k]) { if(BASE>=PMAX-BLOCK && k>block-1000) printf("%I64d\t",k+BASE);//显示最后1000个连续数中的素数 np++; } } t2 = clock( ); printf("\n%0.1f sec\nTotal: %I64d\n",(t2-t1)/1E3,np); return 0; }本论坛中搜到的 作者yu-hua