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 ; 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 ; 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
< ? php function SieveOf ( $ n ) { $ prime = array ( $ n + 1 ) ; for ( $ i = 0 ; $ i <= $ n ; $ i ++ ) $ prime [ $ i ] = true ; for ( $ p = 2 ; $ p * $ p <= $ n ; $ p ++ ) { if ( $ prime [ $ p ] == true ) { for ( $ i = $ p * 2 ; $ i <= $ n ; $ i += $ p ) $ prime [ $ i ] = false ; } } return $ prime ; } function mersennePrimes ( $ n ) { $ prime = SieveOf ( $ n ) ; for ( $ k = 2 ; ( ( 1 << $ k ) - 1 ) <= $ n ; $ k ++ ) { $ num = ( 1 << $ k ) - 1 ; if ( $ prime [ $ num ] ) echo $ num . " " ; } } $ n = 31 ; echo " Mersenne ▁ prime ▁ numbers ▁ smaller ▁ " . " than ▁ or ▁ equal ▁ to ▁ $ n ▁ " . mersennePrimes ( $ n ) ; ? >