fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. //PRIME SIEVE & OPTIMISATIONS
  5.  
  6.  
  7. void primeSieve(int *p,int n){
  8.  
  9.     p[0] = p[1] = 0;
  10.     p[2] = 1;
  11.  
  12.     //Let us Mark all Odd Numbers as Prime(Initialisations)
  13.     for(int i=3;i<=n;i+=2){
  14.         p[i] = 1;
  15.     }
  16.  
  17.     //Sieve Login to mark non prime numbers as 0
  18.     //1. Optimsation : Iterate only over odd Numbers
  19.     for(int i=3;i<=n;i+=2){
  20.  
  21.         if(p[i]){
  22.             //Mark all the multiples of that number as not prime.
  23.             //2. Optimisation Take a jump of 2i starting from i*i
  24.             for(int j=i*i;j<=n;j+=2*i){
  25.                 p[j] = 0;
  26.             }
  27.         }
  28.  
  29.     }
  30.     return;
  31. }
  32.  
  33.  
  34.  
  35.  
  36. int main() {
  37.     int N = 1000000;
  38.     int p[N] = {0};
  39.     primeSieve(p,100);
  40.     for(int i=0;i<=100;i++){
  41.         if(p[i]){
  42.             cout<<i<<" ";
  43.         }
  44.     }
  45.  
  46. }
  47.  
Success #stdin #stdout 0s 7472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
https://ideone.com/BSkx3B
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!