Segmented Sieve | Java program to print print all primes smaller than n using segmented sieve ; This methid 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 . get ( i ) ( divisible by prime . get ( i ) ) For example , if low is 31 and prime . get ( i ) is 3 , we start with 33. ; Mark multiples of prime . get ( 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 method
import java . util . Vector ; import static java . lang . Math . sqrt ; import static java . lang . Math . floor ; class Test { static void simpleSieve ( int limit , Vector < Integer > prime ) { boolean mark [ ] = new boolean [ limit + 1 ] ; for ( int i = 0 ; i < mark . length ; i ++ ) mark [ i ] = 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 . add ( p ) ; System . out . print ( p + " ▁ " ) ; } } } static void segmentedSieve ( int n ) { int limit = ( int ) ( floor ( sqrt ( n ) ) + 1 ) ; Vector < Integer > prime = new Vector < > ( ) ; simpleSieve ( limit , prime ) ; int low = limit ; int high = 2 * limit ; while ( low < n ) { if ( high >= n ) high = n ; boolean mark [ ] = new boolean [ limit + 1 ] ; for ( int i = 0 ; i < mark . length ; i ++ ) mark [ i ] = true ; for ( int i = 0 ; i < prime . size ( ) ; i ++ ) { int loLim = ( int ) ( floor ( low / prime . get ( i ) ) * prime . get ( i ) ) ; if ( loLim < low ) loLim += prime . get ( i ) ; for ( int j = loLim ; j < high ; j += prime . get ( i ) ) mark [ j - low ] = false ; } for ( int i = low ; i < high ; i ++ ) if ( mark [ i - low ] == true ) System . out . print ( i + " ▁ " ) ; low = low + limit ; high = high + limit ; } } public static void main ( String args [ ] ) { int n = 100 ; System . out . println ( " Primes ▁ smaller ▁ than ▁ " + n + " : " ) ; segmentedSieve ( n ) ; } }