Guest User

Untitled

a guest
Dec 16th, 2018
269
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.95 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std ;
  4.  
  5. int N = 1000000000 ;
  6.  
  7. int status[ (1000000000>>5)+2 ] ;
  8.  
  9. bool CHECK( int n , int pos )  {
  10.  
  11.     return (bool)( n & ( 1 << pos ) ) ;
  12.  
  13. }
  14.  
  15. int SET( int n , int pos )  {
  16.  
  17.     return n = n | ( 1 << pos )  ;
  18.  
  19. }
  20.  
  21. void sieve( void )  {
  22.  
  23.     int i , j , sqrt_N ;
  24.  
  25.     sqrt_N = sqrt((double)N) ;
  26.  
  27.     for( i = 3 ; i <= sqrt_N ; i += 2 )  {
  28.  
  29.         if( CHECK( status[i>>5] , i & 31 ) == 0 )  {
  30.  
  31.             for( j = i*i ; j <= N ; j += ( i << 1 ) ) {
  32.  
  33.                 status[j>>5] = SET( status[j>>5] , j & 31 ) ;
  34.  
  35.             }
  36.  
  37.         }
  38.  
  39.     }
  40.  
  41. }
  42.  
  43. int main()
  44.  
  45. {
  46.  
  47.     sieve() ;
  48.  
  49.     int gona = 1 , flag = 501 ;
  50.  
  51.     printf("2\n") ;
  52.  
  53.     for( int i = 3 ; i <= N ; i += 2 )  {
  54.  
  55.         if( CHECK( status[i>>5] , i & 31 ) == 0 )  {
  56.  
  57.             gona++ ;
  58.  
  59.         }
  60.  
  61.         if( gona == flag )  {
  62.  
  63.             flag = flag + 500 ;
  64.  
  65.             printf("%d\n",i) ;
  66.  
  67.         }
  68.  
  69.     }
  70.  
  71.     return 0 ;
  72.  
  73. }
Add Comment
Please, Sign In to add comment