Hi i saw this problem and i only knew how to solve it in array..
is there a different way ??
Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
An efficient way to generate prime numbers from 2 to n is a sieve algorithm.
The simplest prime number sieve is the Sieve of Eratosthenes
For this particular problem, n can be quite large, and a full sieve up to n would be expensive.
However, n-m is quite small (n-m) < 100000; we do not need a full sieve; a partial sieve with a size of n-m+1 would suffice.
// copy all prime numbers between m and n to stm
void copy_primes_between( int m, int n, std::ostream& stm )
// invariant: m >1, m < n , n <= 1000000000
// invariant: (n-m) <= 100000
// generate a partial sieve from m to n
std::vector<bool> sieve( n-m+1, true ) ;
// knock off all the even numbers
for( int i = m%2 ? m+1 : m ; i <= n ; i += 2 ) sieve[i-m] = false ;
if( m == 2 ) sieve = true ;
// and then multiples of odd numbers
const int rootn = std::sqrt(n) + 1 ;
for( int p = 3 ; p <= rootn ; p += 2 )
for( int i = (m/p)*p ; i<=n ; i += p ) if( i != p && i>=m ) sieve[i-m] = false ;
// write the prime numbers out
for( std::size_t i = 0 ; i < sieve.size() ; ++i )
if( sieve[i] ) stm << m+i << '\n' ;
copy_primes_between( 990000000, 990001000, std::cout ) ;