fork download
copy 
  1. #include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4. int primes[10000000];// stores prime upto a max value
  5. int prime[10000000];//stores prime in a given range
  6. int main()
  7. {
  8.   long long int t,m,n,s,k,q;
  9.   for(long long int i=1;i<=1000000;i++){
  10.       primes[i]=1;
  11.       primes[1]=0;
  12.   }
  13.  
  14.     //stores prime using sieve    
  15.     for(long long int i=2;i<=sqrt(1000000);i++) 
  16.     {
  17.         if(primes[i]==1)
  18.         {
  19.             for(long long int j=2;i*j<=1000000;j++)
  20.             {
  21.                 primes[i*j]=0;
  22.             }
  23.         }   
  24.     }
  25.     cin>>t;
  26.     while(t--)
  27.     {
  28.         cin>>m>>n;
  29.         //marking all indices as 1 
  30.         for(long long int i=m;i<=n;i++)      
  31.         {
  32.           prime[i]=1;
  33.         }
  34.         //calculating which offset to mark
  35.         for(long long int i=2;i<=n-m+1;i++)       
  36.         {
  37.             if(primes[i]==1)
  38.             {
  39.                 long long int x=(m/i)*i;
  40.                 while(x<m)
  41.                 x=x+i;   
  42.                 for(long long int j=x;j<=n;j=j+i)
  43.                 {
  44.                     if(primes[j]==0)
  45.                     prime[j]=0;
  46.                }  
  47.              }
  48.            }         
  49.         for(long long int i=m;i<=n;i++)
  50.         {
  51.             if(prime[i]==1&&i!=1)
  52.             cout<<i<<"\n";
  53.         }
  54.     }
  55.     return 0;
  56. }
Runtime error #stdin #stdout 0.02s 81536KB
comments (?)
stdin
copy 
1
100000000 100000009
stdout
copy 
Standard output is empty
https://ideone.com/8YsK7k
language:
C++ (gcc 8.3)
created:
7 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!