title: Print first 1 million primes in 1 sec with constraints program size 50000 bytes and limited Memory
body: <p>I tried sieve of Eratosthenes: Following is my code:</p>
  
  <pre><code>void prime_eratos(int N) {
      int root = (int)sqrt((double)N);
      bool *A = new bool[N + 1];
      memset(A, 0, sizeof(bool) * (N + 1));
      for (int m = 2; m &lt;= root; m++) {
          if (!A[m]) {
              printf("%d  ",m);
              for (int k = m * m; k &lt;= N; k += m)
                  A[k] = true;
          }
      }
  
      for (int m = root; m &lt;= N; m++)
          if (!A[m])
              printf("%d  ",m);
      delete [] A; 
  }
  
  int main(){
  
      prime_eratos(179426549);
      return 0;
  }
  </code></pre>
  
  <p>It took time : real 7.340s in my system.</p>
  
  <p>I also tried Sieve of Atkins(studied somewhere faster than 
      sieve of Eratosthenes).</p>
  
  <p>But in my case,it took time : real 10.433s .</p>
  
  <p>Here is the code:</p>
  
  <pre><code>int main(){
      int limit=179426549;
      int x,y,i,n,k,m;
      bool *is_prime = new bool[179426550];
  
      memset(is_prime, 0, sizeof(bool) * 179426550);
  
      /*for(i=5;i&lt;=limit;i++){
        is_prime[i]=false;
        }*/
      int N=sqrt(limit);
      for(x=1;x&lt;=N;x++){
          for(y=1;y&lt;=N;y++){
              n=(4*x*x) + (y*y);
              if((n&lt;=limit) &amp;&amp;(n%12 == 1 || n%12==5))
                  is_prime[n]^=true;
              n=(3*x*x) + (y*y);
              if((n&lt;=limit) &amp;&amp; (n%12 == 7))
                  is_prime[n]^=true;
              n=(3*x*x) - (y*y);
              if((x&gt;y) &amp;&amp; (n&lt;=limit) &amp;&amp; (n%12 == 11))
                  is_prime[n]^=true;
          }
      }
      for(n=5;n&lt;=N;n++){
          if(is_prime[n]){
              m=n*n;
              for(k=m;k&lt;=limit;k+=m)
                  is_prime[k]=false;
  
          }
      }
      printf("2   3   ");
      for(n=5;n&lt;=limit;n++){
          if(is_prime[n])
              printf("%d   ",n);
      }
      delete []is_prime;
      return 0;
  }
  </code></pre>
  
  <p>Now,I wonder,none is able to output 1 million primes in 1 sec.</p>
  
  <p>One approach could be: </p>
  
  <pre><code>     I store the values in Array but the program size is limited.
  </code></pre>
  
  <p>Could someone suggest me some way to get first 1 million primes in less</p>
  
  <p>than a sec satisfying the constraints(discussed above) ?</p>
  
  <p>Thanx !! </p>