fork download
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define MAXN 10000000
  6.  
  7. int lp1[MAXN+1];
  8.  
  9. void sieve1( int n )
  10. {
  11. lp1[0]=lp1[1]=1;
  12.  
  13. for(int i=2;i<=n;i+=2) lp1[i]=2;
  14.  
  15. for(int i=3;i*i<=n;i+=2)
  16. {
  17. if(lp1[i]==0)
  18. for(int j=i*i;j<=n;j+=2*i)
  19. if(lp1[j]==0) lp1[j]=i;
  20. }
  21.  
  22. for(int i=2;i<=n;i++)
  23. if(lp1[i]==0) lp1[i]=i;
  24. }
  25.  
  26. int lp2[MAXN+1];
  27. int pc = 0, pr[MAXN/10]; /* if MAXN >= 1000000 */
  28.  
  29. void sieve2( int n )
  30. {
  31. lp2[0] = lp2[1] = 1;
  32. for( int i = 2; i <= n; ++i)
  33. {
  34. if( lp2[i] == 0 ) pr[pc++] = lp2[i] = i;
  35. for( int j = 0; j < pc; ++j)
  36. {
  37. int x = i * pr[j];
  38. if( x > n ) break;
  39. if( lp2[x] == 0 ) lp2[x] = pr[j];
  40. if( lp2[i] == pr[j] ) break;
  41. }
  42. }
  43. }
  44.  
  45. int main()
  46. {
  47. auto t1a = clock();
  48. sieve1( MAXN );
  49. auto t1b = clock();
  50. cout << "general sieve: " << ((double) (t1b - t1a)) / CLOCKS_PER_SEC << endl;
  51. auto t2a = clock();
  52. sieve2( MAXN );
  53. auto t2b = clock();
  54. cout << "linear sieve: " << ((double) (t2b - t2a)) / CLOCKS_PER_SEC << endl;
  55. for( int i = 0; i <= MAXN; ++i)
  56. if( lp1[i] != lp2[i] )
  57. cout << "Wrong lp for i = " << i << endl;
  58. return 0;
  59. }
  60.  
Success #stdin #stdout 0.16s 84352KB
stdin
Standard input is empty
stdout
general sieve: 0.084176
linear sieve: 0.072962