Print all safe primes below N | Python 3 implementation of the approach ; Function to print first n safe primes ; Initialize all entries of integer array as 1. A value in prime [ i ] will finally be 0 if i is Not a prime , else 1 ; 0 and 1 are not primes ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; If i is prime ; 2 p + 1 ; If 2 p + 1 is also a prime then set prime [ 2 p + 1 ] = 2 ; i is a safe prime ; Driver code
from math import sqrt NEW_LINE def printSafePrimes ( n ) : NEW_LINE INDENT prime = [ 0 for i in range ( n + 1 ) ] NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT prime [ i ] = 1 NEW_LINE DEDENT prime [ 0 ] = prime [ 1 ] = 0 NEW_LINE for p in range ( 2 , int ( sqrt ( n ) ) + 1 , 1 ) : NEW_LINE INDENT if ( prime [ p ] == 1 ) : NEW_LINE INDENT for i in range ( p * 2 , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = 0 NEW_LINE DEDENT DEDENT DEDENT for i in range ( 2 , n + 1 , 1 ) : NEW_LINE INDENT if ( prime [ i ] != 0 ) : NEW_LINE INDENT temp = ( 2 * i ) + 1 NEW_LINE if ( temp <= n and prime [ temp ] != 0 ) : NEW_LINE INDENT prime [ temp ] = 2 NEW_LINE DEDENT DEDENT DEDENT for i in range ( 5 , n + 1 ) : NEW_LINE INDENT if ( prime [ i ] == 2 ) : NEW_LINE INDENT print ( i , end = " ▁ " ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 20 NEW_LINE printSafePrimes ( n ) NEW_LINE DEDENT