What is the 5761455th prime number?

找出所有小于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

Leave a Reply

Your e-mail address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.