You are here:

C++/c++ question

Advertisement


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.

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

C++

All Answers


Answers by Expert:


Ask Experts

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

about 15 years or so

Education/Credentials
post graduate engineer

©2016 About.com. All rights reserved.