Sieve of Sundaram to print all primes smaller than n | Prints all prime numbers smaller ; In general Sieve of Sundaram , produces primes smaller than ( 2 * x + 2 ) for a number given number x . Since we want primes smaller than n , we reduce n to half ; This array is used to separate numbers of the form i + j + 2 ij from others where 1 <= i <= j Initialize all elements as not marked ; Main logic of Sundaram . Mark all numbers of the form i + j + 2 ij as true where 1 <= i <= j ; Since 2 is a prime number ; Print other primes . Remaining primes are of the form 2 * i + 1 such that marked [ i ] is false . ; Driver Code
def SieveOfSundaram ( n ) : NEW_LINE INDENT nNew = int ( ( n - 1 ) / 2 ) ; NEW_LINE marked = [ 0 ] * ( nNew + 1 ) ; NEW_LINE for i in range ( 1 , nNew + 1 ) : NEW_LINE INDENT j = i ; NEW_LINE while ( ( i + j + 2 * i * j ) <= nNew ) : NEW_LINE INDENT marked [ i + j + 2 * i * j ] = 1 ; NEW_LINE j += 1 ; NEW_LINE DEDENT DEDENT if ( n > 2 ) : NEW_LINE INDENT print ( 2 , end = " ▁ " ) ; NEW_LINE DEDENT for i in range ( 1 , nNew + 1 ) : NEW_LINE INDENT if ( marked [ i ] == 0 ) : NEW_LINE INDENT print ( ( 2 * i + 1 ) , end = " ▁ " ) ; NEW_LINE DEDENT DEDENT DEDENT n = 20 ; NEW_LINE SieveOfSundaram ( n ) ; NEW_LINE