You are here:

C++/c++ 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!
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.$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 ) ;


All Answers

Answers by Expert:

Ask Experts




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

post graduate engineer

©2017 All rights reserved.

[an error occurred while processing this directive]