找出所有小于M的素数。
当M＝100,000,000时，得到标题的答案。
Result:
MiffyLiye@MiffyLiye:~/Workspace/Prime> uname -i
x86_64
MiffyLiye@MiffyLiye:~/Workspace/Prime> icc prime.c -o prime.out
MiffyLiye@MiffyLiye:~/Workspace/Prime> time ./prime.out
real 0m3.475s
user 0m3.164s
sys 0m0.108s
MiffyLiye@MiffyLiye:~/Workspace/Prime> ls -l Primes.txt
-rw-r--r-- 1 MiffyLiye users 51099000 2009-05-25 16:35 Primes.txt
MiffyLiye@MiffyLiye:~/Workspace/Prime> cat -b Primes.txt | tail
5761446 99999787
5761447 99999821
5761448 99999827
5761449 99999839
5761450 99999847
5761451 99999931
5761452 99999941
5761453 99999959
5761454 99999971
5761455 99999989
MiffyLiye@MiffyLiye:~/Workspace/Prime>
C code:
01 // Prime 0
02 // N>0
03 #include<stdio.h>
04 #define N 12500000LL
05 #define Set(a,n) {a[n/8]=(a[n/8]|(0×01<<(n%8)));}
06 #define Get(a,n) ((a[n/8]>>(n%8))&0×01)
07 int main()
08 {
09 long long i,j;
10 char *a=malloc(N);
11 if(a==NULL){
12 printf(“Failed!\n“);
13 return 1;
14 }
15 for(i=0;i<N;i++)
16 a[i]=0×0;
17 for(i=3;i<(8*N);i+=2)
18 if(Get(a,i)==0×0)
19 for(j=i;(i*j)<(8*N);j+=2)
20 Set(a,i*j);
21 FILE *fp;
22 fp=fopen(“Primes.txt”,“w”);
23 if(fp==NULL){
24 printf(“Can’t creat Primes.txt for writing!\n“);
25 return 2;
26 }
27 printf(“Begin writing data to Primes.txt.\nThis may take some time.\n”);
28 fprintf(fp,“2\n“);
29 for(i=3;i<8*N;i+=2)
30 if(Get(a,i)==0)
31 fprintf(fp,“%lld\n“,i);
32 fclose(fp);
33 free(a);
34 return 0;
35 }
36
Code converted to C++:
01 #include<iostream>
02 #include<algorithm>
03 #include<vector>
04 using std::vector;
05 using std::fill;
06 using std::cout;
07 using std::endl;
08
09 template<typename F>
10 struct Final_action{
11 Final_action(F f): clean{f} {}
12 ~Final_action() {clean();}
13 F clean;
14 };
15
16 template<class F>
17 Final_action<F> finally(F f)
18 {
19 return Final_action<F>(f);
20 }
21
22 int main()
23 {
24 const int n=100000000;
25
26 bool* a=new bool[n];
27 auto act=finally([&]{delete[] a;});
28 fill(&a[0],&a[n],true);
29 a[0]=false;
30 a[1]=false;
31 vector<int> primes;
32 for(long long i=0;i<n;++i){
33 if(a[i]){
34 primes.push_back(i);
35 for(long long j=i;(i*j)<n;++j){
36 a[i*j]=false;
37 }
38 }
39 }
40
41 auto count=primes.size();
42 const int tail=10;
43 for(int i=count-tail;i<count;++i){
44 cout<<(i+1)<<'\t'<<primes[i]<<endl;
45 }
46
47 return 0;
48 }
49