You are here:

# C++/c++ question

Question
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 ) ;
}

Questioner's Rating
 Rating(1-10) Knowledgeability = 10 Clarity of Response = 8 Politeness = 10 Comment No Comment

C++

Volunteer

#### vijayan

##### Expertise

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.

##### Experience

Education/Credentials