You are here:

- Home
- Computing/Technology
- C/C++
- C++
- c++ question

Advertisement

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!

Input

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.

Output

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

http://en.wikipedia.org/wiki/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.

http://liveworkspace.org/code/235Fap$2

#include <iostream>

#include <vector>

#include <cmath>

// 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[0] = 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' ;

}

int main()

{

std::cout.sync_with_stdio(false) ;

copy_primes_between( 990000000, 990001000, std::cout ) ;

}

- Add to this Answer
- Ask a Question

Rating(1-10) | Knowledgeability = 10 | Clarity of Response = 8 | Politeness = 10 |

Comment | No Comment |

my primary areas of interest are generic and template metaprogramming, STL, algorithms, design patterns and c++11. i would not answer questions about gui and web programming.

about 15 years or so**Education/Credentials**

post graduate engineer