fork(4) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int N = 1e7;
  4. bool comp[N];
  5. vector<int>primes;
  6. void oldsieve()
  7. {
  8.     memset(comp,0,sizeof comp);
  9.     primes.clear();
  10.     for(int i=2;i<N;i++)
  11.         if(!comp[i])
  12.         {
  13.             primes.push_back(i);
  14.             for(int j=i*2;j<N;j+=i)
  15.                 comp[j]=1;
  16.         }
  17. }
  18. void newsieve()
  19. {
  20.     memset(comp,0,sizeof comp);
  21.     primes.clear();
  22.     for(int i=2;i<N;i++)
  23.     {
  24.         if(!comp[i])
  25.             primes.push_back(i);
  26.             for(int j=0,si=primes.size();j<si&&i*primes[j]<N;j++)
  27.             {
  28.                 comp[primes[j]*i]=1;
  29.                 if(i%primes[j]==0)break;
  30.             }
  31.     }
  32. }
  33. int main()
  34. {
  35.     time_t t0;
  36.     time(&t0);
  37.     oldsieve();
  38.     //for(int i=0;i<20;i++)cout<<primes[i]<<' ';cout<<endl;
  39.     newsieve();
  40.     //for(int i=0;i<20;i++)cout<<primes[i]<<' ';cout<<endl;
  41.     time_t t1;
  42.     time(&t1);
  43.     double seconds = difftime(t1,t0);
  44.     printf("%.7f",seconds);
  45. }
Success #stdin #stdout 0.13s 25000KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0000000
https://ideone.com/oww5Qj
language:
C++14 (gcc 8.3)
created:
6 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!