c语言：输入一个正整数n，统计小于n的素数个数

美丽的海洋

如题，求解，萌新。百度不到

江南老顽童

1. #include <stdio.h>
   
2. #include <math.h>  //因为要用到sqrt()函数
   
3. int main()
   
4. {
   
5. int i,j,flag;
   
6. int n,num=0;   //num记录素数的个数
   
7. 
   
8. scanf("%d",&n);   
   
9. for(i=1;i<=n;i++)     // 从1到n找数
   
10. {
    
11. flag=1;           //为1时表示i为素数，为0则表示i不是素数
    
12. for (j=2;j<=sqrt(i);j++)  // a/b=c，如果b,c不等，则b,c里面的最小值一定小于sqrt(a)，所以判断到sqrt(a)就可以
    
13. {
    
14. if(i%j==0)    //不是素数，修改标志推出for循环
    
15. {
    
16. flag=0;
    
17. break;
    
18. }
    
19. }
    
20. if(flag==1)      //判断是否是素数，
    
21. {
    
22. printf("%d为素数。\n",i);
    
23. num++;        
    
24. }
    
25. }
    
26. 
    
27. printf("%d",num);
    
28. return 0;
    
29. }

复制代码

王四福

1. #include <stdio.h>
   
2. #include <math.h>  //因为要用到sqrt()函数
   
3. 
   
4. int main()
   
5. {
   
6.     int i,j,flag;
   
7.     int n, num = 0;   //num记录素数的个数
   
8. 
   
9.     scanf("%d", &n);
   
10.     if (n < 2) {
    
11.         printf("No prime!\n");
    
12.         return -1;
    
13.     }
    
14.     //for(i = 1; i <= n; i++)     // 从1到n找数
    
15.     num = 1; //2 is prime
    
16.     printf("%d为素数。\n", 2);
    
17.     for(i = 3; i <= n; i = i + 2)     // 从1到n找数
    
18.     {
    
19.         flag=1;           //为1时表示i为素数，为0则表示i不是素数
    
20.         for (j=2;j<=sqrt(i);j++)  // a/b=c，如果b,c不等，则b,c里面的最小值一定小于sqrt(a)，所以判断到sqrt(a)就可以
    
21.         {
    
22.             if(i%j==0)    //不是素数，修改标志推出for循环
    
23.             {
    
24.                 flag=0;
    
25.                 break;
    
26.             }
    
27.         }
    
28.         if(flag==1)      //判断是否是素数，
    
29.         {
    
30.             printf("%d为素数。\n",i);
    
31.             num++;
    
32.         }
    
33.     }
    
34. 
    
35.     printf("%d",num);
    
36.     return 0;
    
37. }

复制代码

新的天空

https://github.com/kimwalisch/primesieve   用这个筛法的吧, 速度比较可以, 筛法复杂度在 O(N*lnlnN)  ...  我本子上试了下求 1E12 范围内有 37607912018 个素数, 用时  37.3 秒...
不过指定范围素数个数有 O(N^(2/3 + ε)) 的算法,  仔细写能比这个更快些 ...

小会

1. 很多年前改写的 intfree 求素数个数的 Pascal 代码,  O(N^(2/3 + ε)),  是比 primesieve 快不少,  
   
2. 求 500000000000 以内的素数个数,  primesieve 八线程用时  12.9 秒, 单线程用时 89.8秒,  下面的代码单线程用时 10.8 秒, 就是没写成多线程的...
   
3. 
   
4. 
   
5. #include <stdio.h>
   
6. #include <stdlib.h>
   
7. #include <time.h>
   
8. #include <math.h>
   
9.   
   
10. #define XPREVN        (64*1024*1024)                /**/
    
11. #define XSQRTPREVN    (8*1024)
    
12. #define XPREVPI        (4*1024*1024)                /* PI(XPREVN) : 3957809 */
    
13. #define XMAXPIX           ((LLong)512 << 30)
    
14. #define XMAXNTH        ((LLong)10*1000*1000*1000)    /* NTH( 1E10 ) == 252097800623 */
    
15.   
    
16. int        *X_small_prime ,  X_pi_small_prime;
    
17. int        *X_pi_prev_N   , *X_prev_V;
    
18.   
    
19. #define XPREVDM        (7)
    
20. #define XPREVQ        (2*3*5*7*11*13*17)
    
21. #define XPREVPHQ    (1*2*4*6*10*12*16)
    
22.   
    
23. #ifdef _MSC_VER
    
24. #pragma warning( disable : 4244 )
    
25. typedef __int64        LLong;
    
26. #define LLFmt        "I64d"
    
27. #else
    
28. typedef long long    LLong;
    
29. #define LLFmt        "Ld"
    
30. #endif
    
31.   
    
32. static LLong phiX_p( LLong x , LLong a )
    
33. {
    
34.     if( a == XPREVDM )
    
35.         return x / XPREVQ * XPREVPHQ + X_prev_V[ x % XPREVQ ];
    
36.     if( x < X_small_prime[a-1] )
    
37.         return 1;
    
38.     return phiX_p( x , a - 1 ) - phiX_p( x / X_small_prime[a-1] , a - 1 );   
    
39. }
    
40.   
    
41.   
    
42.   
    
43. LLong phiX( LLong X )
    
44. {
    
45.     LLong cubeRootX  , max , len3 , len2 , s , i , k;
    
46.     LLong sum , p;
    
47.     if( X <= XPREVN )
    
48.         return X_pi_prev_N[X];
    
49.       
    
50.     max   = (LLong)(pow( (double)X , 2./3 ) + 2);
    
51.     cubeRootX = (LLong)(pow( (double)X , 1./3 ) + .5);
    
52.     if( cubeRootX*cubeRootX*cubeRootX > X )
    
53.         --cubeRootX;
    
54.     len3 = X_pi_prev_N[cubeRootX];
    
55.       
    
56.     sum = 0; s = 0; k = max -1 ;
    
57.     for( i = len3; ;++i )
    
58.     {
    
59.         p = X_small_prime[i];
    
60.         if( p * p > X ) break;
    
61.          
    
62.         s += X_pi_prev_N[k] - X_pi_prev_N[(int)((double)X/p)];
    
63.         k = (int)((double)X/p);
    
64.          
    
65.         sum += s;
    
66.     }
    
67.     len2 = X_pi_prev_N[p-1];
    
68.       
    
69.     sum = (len2-len3)*X_pi_prev_N[max-1] - sum;
    
70.     sum = len3 * (len3-1)/2 - len2 * (len2-1) / 2 + sum;
    
71.       
    
72.     return phiX_p( X , len3 ) - sum + len3 - 1;
    
73. }
    
74.   
    
75. void initSmallPrime()
    
76. {
    
77.     char *mark = (char*)calloc(1,XPREVN/2+1);
    
78.     int i , j;
    
79.     X_small_prime = (int*)calloc(sizeof(int),XPREVPI );
    
80.     X_pi_prev_N   = (int*)calloc(sizeof(int),XPREVN+1);
    
81.     X_prev_V      = (int*)calloc(sizeof(int),XPREVQ+1);
    
82.       
    
83.     for( i = 3; i <= XSQRTPREVN; i += 2 )
    
84.     {
    
85.         if( mark[i/2] ) continue;
    
86.         for( j = i*i/2; j <= XPREVN/2; j+=i )
    
87.             mark[j] = 1;
    
88.     }
    
89.     X_small_prime[0] = 2;
    
90.     X_pi_small_prime = 1;
    
91.     X_pi_prev_N[0] = X_pi_prev_N[1] = 0;
    
92.     X_pi_prev_N[2] = 1;
    
93.     for( i = 3; i <= XPREVN; i += 2 )
    
94.     {
    
95.         if( mark[i/2] )
    
96.         {
    
97.             X_pi_prev_N[i+1] = X_pi_prev_N[i] = X_pi_prev_N[i-1];
    
98.         }
    
99.         else
    
100.         {
     
101.             X_pi_prev_N[i+1] = X_pi_prev_N[i] = 1 + X_pi_prev_N[i-1];
     
102.             X_small_prime[X_pi_small_prime++] = i;
     
103.         }
     
104.     }
     
105.     free(mark);
     
106.       
     
107.     for( i = 0; i < XPREVQ; ++i )
     
108.         X_prev_V[i] = i;
     
109.     for( i = 1; i <= XPREVDM; ++i )
     
110.         for( j = XPREVQ-1; j >= 0; --j )
     
111.             X_prev_V[j] -= X_prev_V[ j/X_small_prime[i-1] ];
     
112. }
     
113.   
     
114. int main()
     
115. {
     
116.     LLong a;
     
117.     clock_t now = clock();
     
118.     initSmallPrime();
     
119.     printf( "init time used : %lf seconds\n" , (double)(clock() - now) / CLOCKS_PER_SEC);
     
120.   
     
121.     while( 1 == scanf( "%" LLFmt , &a ) )
     
122.     {
     
123.         if( a <= 0 )
     
124.             break;
     
125.         else if( a <= XMAXPIX )
     
126.         {
     
127.             now = clock();
     
128.             printf( "phiX( %" LLFmt " ) == %" LLFmt "\n" , a , phiX( a ) );
     
129.             printf( "phiX time used : %lf seconds\n" , (double)(clock() - now) / CLOCKS_PER_SEC );
     
130.         }
     
131.         else
     
132.             printf( "%" LLFmt " Out of range\n" , a );
     
133.     }
     
134.       
     
135.     return 0;
     
136. }

复制代码