Segmented Sieve | C ++ program to print print all primes smaller than n using segmented sieve ; This functions finds all primes smaller than ' limit ' using simple sieve of eratosthenes . It also stores found primes in vector prime [ ] ; Create a boolean array " mark [ 0 . . n - 1 ] " and initialize all entries of it as true . A value in mark [ p ] will finally be false if ' p ' is Not a prime , else true . ; If p is not changed , then it is a prime ; Update all multiples of p ; Print all prime numbers and store them in prime ; Prints all prime numbers smaller than ' n ' ; Compute all primes smaller than or equal to square root of n using simple sieve ; Divide the range [ 0. . n - 1 ] in different segments We have chosen segment size as sqrt ( n ) . ; While all segments of range [ 0. . n - 1 ] are not processed , process one segment at a time ; To mark primes in current range . A value in mark [ i ] will finally be false if ' i - low ' is Not a prime , else true . ; Use the found primes by simpleSieve ( ) to find primes in current range ; Find the minimum number in [ low . . high ] that is a multiple of prime [ i ] ( divisible by prime [ i ] ) For example , if low is 31 and prime [ i ] is 3 , we start with 33. ; Mark multiples of prime [ i ] in [ low . . high ] : We are marking j - low for j , i . e . each number in range [ low , high ] is mapped to [ 0 , high - low ] so if range is [ 50 , 100 ] marking 50 corresponds to marking 0 , marking 51 corresponds to 1 and so on . In this way we need to allocate space only for range ; Numbers which are not marked as false are prime ; Update low and high for next segment ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; void simpleSieve ( int limit , vector < int > & prime ) { vector < bool > mark ( limit + 1 , true ) ; for ( int p = 2 ; p * p < limit ; p ++ ) { if ( mark [ p ] == true ) { for ( int i = p * p ; i < limit ; i += p ) mark [ i ] = false ; } } for ( int p = 2 ; p < limit ; p ++ ) { if ( mark [ p ] == true ) { prime . push_back ( p ) ; cout << p << " ▁ " ; } } } void segmentedSieve ( int n ) { int limit = floor ( sqrt ( n ) ) + 1 ; vector < int > prime ; prime . reserve ( limit ) ; simpleSieve ( limit , prime ) ; int low = limit ; int high = 2 * limit ; while ( low < n ) { if ( high >= n ) high = n ; bool mark [ limit + 1 ] ; memset ( mark , true , sizeof ( mark ) ) ; for ( int i = 0 ; i < prime . size ( ) ; i ++ ) { int loLim = floor ( low / prime [ i ] ) * prime [ i ] ; if ( loLim < low ) loLim += prime [ i ] ; for ( int j = loLim ; j < high ; j += prime [ i ] ) mark [ j - low ] = false ; } for ( int i = low ; i < high ; i ++ ) if ( mark [ i - low ] == true ) cout << i << " ▁ " ; low = low + limit ; high = high + limit ; } } int main ( ) { int n = 100000 ; cout << " Primes ▁ smaller ▁ than ▁ " << n << " : n " ; segmentedSieve ( n ) ; return 0 ; }