fork download
copy 
  1. #include<iostream>
  2. #include<cmath>
  3. #define diff 100000
  4. #define sq   1000000000
  5. int prime[diff];
  6. int myprime[diff];
  7. using namespace std;
  8.  
  9.    int main()
  10.     {
  11.     long long int m,n,i,j,q,s,r,w,p;
  12.     int t,range;
  13.       r=0;
  14.       for(i=2;i<=sqrt(sq);i++)  //marking all prime numbers upto sqrt(10^9)
  15.            {
  16.                prime[i]=1;
  17.            }
  18.       for(i=2;i<=sqrt(sq);i++)   //marking all non-prime upto sqrt(10^9)
  19.           {
  20.             if(prime[i]==1)
  21.                {
  22.                 for(j=2;i*j<=sqrt(sq);j++)
  23.                    {
  24.                     prime[i*j]=0;
  25.                    }
  26.  
  27.                 }
  28.            }
  29.  
  30.         for(i=2;i<=sqrt(sq);i++)    //Storing all prime number upto sqrt(10^9) in array
  31.             {
  32.               if(prime[i]==1)
  33.                 {
  34.                  myprime[r]=i;
  35.                  r++;
  36.                 }
  37.             }
  38.        cin>>t;
  39.        while(t--)
  40.          {
  41.            cin>>m>>n;
  42.            range=floor(sqrt(((double)n)));
  43.            prime[0]=0;
  44.            prime[1]=0;
  45.             for(i=0;i<r;i++)   //marking all prime in the range
  46.             {
  47.  
  48.  
  49.                w=m/myprime[i];
  50.                w=w*myprime[i];
  51.                p=myprime[i];
  52. // The following code is incorrect as I am unable to derive out the logic to mark the multiples in the range
  53.  
  54.                for(j=w;j<=n;j=j+p)   //j+2<n
  55.                  {
  56.                  prime[j+p]=0;
  57.                  }
  58.              }
  59.  
  60.            for(i=m;i<=n;i++)
  61.            {
  62.                if(prime[i]==1)
  63.                {
  64.                    cout<<i<<"\n";
  65.  
  66.                }
  67.            }
  68.            cout<<"\n";
  69.         }
  70.      return 0;
  71.     }
  72.  
Runtime error #stdin #stdout 0s 4236KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ryhi9Q
language:
C++ (gcc 8.3)
created:
8 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!