fork(1) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. int main()
  4. {
  5. long int a,c,k,d;  // 100k: 4.4 secs ; 120k: 6.13 ; logBase( 1.2, 6.13/4.4) = 1.82: T ~ n^1.82
  6. k=0;
  7. cin>>a;            // 1mln projected run time = 4.4*10^1.82 =~ 290 secs
  8. cin>>d;
  9. long int b[a];
  10. b[a-1]=0;
  11. for(long int i=2;i<=a;i++)
  12. {
  13.     for(long int j=2;j<=(i/j);j++)  // WAS SLOW: j<=(i/2); 
  14.     {
  15.         c=1;             // NOW FAST: j<=(i/j); 1mln: 1.28 secs; 2mln: 3.47; T ~ n^1.44
  16.         if ( i%j!=0 )
  17.         {
  18.             continue;
  19.         }    
  20.         else 
  21.         {
  22.             c=0;
  23.             break;
  24.         }   
  25.     }
  26.     if (c!=0)
  27.         {
  28.              b[k]=i;
  29.              //++k;
  30.         }
  31.     else b[k]=0;
  32.     ++k;
  33.  }
  34.  for(long int i=d;i<a;i++)
  35.  {
  36.      if (b[i]!=0)
  37.      {
  38.           cout<<b[i]<<"\t";
  39.      }         
  40.  }   
  41.  cin.ignore();
  42.  cin.get();
  43.  return 0;
  44.  }
Success #stdin #stdout 1.27s 6684KB
comments ()
stdin
copy 
1000100  999970
stdout
copy 
999979	999983	1000003	1000033	1000037	1000039	1000081	1000099
https://ideone.com/uGChuR
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!