Mersenne Prime | Generate all prime numbers less than n . ; Initialize all entries of boolean array as true . A value in prime [ i ] will finally be false if i is Not a prime , else true bool prime [ n + 1 ] ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Function to generate mersenne primes less than or equal to n ; Create a boolean array " prime [ 0 . . n ] " ; Generating primes using Sieve ; Generate all numbers of the form 2 ^ k - 1 and smaller than or equal to n . ; Checking whether number is prime and is one less then the power of 2 ; Driver Code
def SieveOfEratosthenes ( n , prime ) : NEW_LINE INDENT for i in range ( 0 , n + 1 ) : NEW_LINE INDENT prime [ i ] = True NEW_LINE DEDENT p = 2 NEW_LINE while ( p * p <= n ) : NEW_LINE INDENT if ( prime [ p ] == True ) : NEW_LINE INDENT for i in range ( p * 2 , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT DEDENT def mersennePrimes ( n ) : NEW_LINE INDENT prime = [ 0 ] * ( n + 1 ) NEW_LINE SieveOfEratosthenes ( n , prime ) NEW_LINE k = 2 NEW_LINE while ( ( ( 1 << k ) - 1 ) <= n ) : NEW_LINE INDENT num = ( 1 << k ) - 1 NEW_LINE if ( prime [ num ] ) : NEW_LINE INDENT print ( num , end = " ▁ " ) NEW_LINE DEDENT k += 1 NEW_LINE DEDENT DEDENT n = 31 NEW_LINE print ( " Mersenne ▁ prime ▁ numbers ▁ smaller " , " than ▁ or ▁ equal ▁ to ▁ " , n ) NEW_LINE mersennePrimes ( n ) NEW_LINE