Segmented Sieve | Python3 program to print all primes smaller than n , using segmented sieve ; This method finds all primes smaller than ' limit ' using simple sieve of eratosthenes . It also stores found primes in list prime ; Create a boolean list " 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 Code
import math NEW_LINE prime = [ ] NEW_LINE def simpleSieve ( limit ) : NEW_LINE INDENT mark = [ True for i in range ( limit + 1 ) ] NEW_LINE p = 2 NEW_LINE while ( p * p <= limit ) : NEW_LINE INDENT if ( mark [ p ] == True ) : NEW_LINE INDENT for i in range ( p * p , limit + 1 , p ) : NEW_LINE INDENT mark [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT for p in range ( 2 , limit ) : NEW_LINE INDENT if mark [ p ] : NEW_LINE INDENT prime . append ( p ) NEW_LINE print ( p , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT ' NEW_LINE def segmentedSieve ( n ) : NEW_LINE INDENT limit = int ( math . floor ( math . sqrt ( n ) ) + 1 ) NEW_LINE simpleSieve ( limit ) NEW_LINE low = limit NEW_LINE high = limit * 2 NEW_LINE while low < n : NEW_LINE INDENT if high >= n : NEW_LINE INDENT high = n NEW_LINE DEDENT mark = [ True for i in range ( limit + 1 ) ] NEW_LINE for i in range ( len ( prime ) ) : NEW_LINE INDENT loLim = int ( math . floor ( low / prime [ i ] ) * prime [ i ] ) NEW_LINE if loLim < low : NEW_LINE INDENT loLim += prime [ i ] NEW_LINE DEDENT for j in range ( loLim , high , prime [ i ] ) : NEW_LINE INDENT mark [ j - low ] = False NEW_LINE DEDENT DEDENT for i in range ( low , high ) : NEW_LINE INDENT if mark [ i - low ] : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT low = low + limit NEW_LINE high = high + limit NEW_LINE DEDENT DEDENT n = 100 NEW_LINE print ( " Primes ▁ smaller ▁ than " , n , " : " ) NEW_LINE segmentedSieve ( 100 ) NEW_LINE