Ohjelma löytää kaikki Mersenne Prime -tuotteet N
Kokeile sitä GfG Practicessa 
Mersennen alkuluku on alkuluku, joka on yksi pienempi kuin kahden potenssi. Toisin sanoen mikä tahansa alkuluku on Mersennen alkuluku, jos se on muotoa 2 k -1, jossa k on kokonaisluku, joka on suurempi tai yhtä suuri kuin 2. Ensimmäiset Mersennen alkuluvut ovat 3 7 31 ja 127.
Tehtävänä on tulostaa kaikki Mersennen alkuluvut pienemmät kuin syötetty positiivinen kokonaisluku n.
Esimerkkejä:
Input: 10
Output: 3 7
3 and 7 are prime numbers smaller than or
equal to 10 and are of the form 2 k -1
Input: 100
Output: 3 7 31
Ideana on generoida kaikki alkuluvut, jotka ovat pienempiä tai yhtä suuria kuin annettu luku n käyttäen Eratosthenesin seula . Kun olemme luoneet kaikki tällaiset alkuluvut, toistamme kaikki muodon 2 numerot k -1 ja tarkista, ovatko ne alkulukuja vai eivät.
Alla idean toteutus.
C++Java// Program to generate mersenne primes #includeusing namespace std ; // Generate all prime numbers less than n. void SieveOfEratosthenes ( int n bool prime []) { // 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]; for ( int i = 0 ; i <= n ; i ++ ) prime [ i ] = true ; for ( int p = 2 ; p * p <= n ; p ++ ) { // If prime[p] is not changed then it // is a prime if ( prime [ p ] == true ) { // Update all multiples of p for ( int i = p * 2 ; i <= n ; i += p ) prime [ i ] = false ; } } } // Function to generate mersenne primes less // than or equal to n void mersennePrimes ( int n ) { // Create a boolean array 'prime[0..n]' bool prime [ n + 1 ]; // Generating primes using Sieve SieveOfEratosthenes ( n prime ); // Generate all numbers of the form 2^k - 1 // and smaller than or equal to n. for ( int k = 2 ; (( 1 < < k ) -1 ) <= n ; k ++ ) { long long num = ( 1 < < k ) - 1 ; // Checking whether number is prime and is // one less than the power of 2 if ( prime [ num ]) cout < < num < < ' ' ; } } // Driven program int main () { int n = 31 ; cout < < 'Mersenne prime numbers smaller ' < < 'than or equal to ' < < n < < endl ; mersennePrimes ( n ); return 0 ; } Python3// Program to generate // mersenne primes import java.io.* ; class GFG { // Generate all prime numbers // less than n. static void SieveOfEratosthenes ( int n boolean prime [] ) { // 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]; for ( int i = 0 ; i <= n ; i ++ ) prime [ i ] = true ; for ( int p = 2 ; p * p <= n ; p ++ ) { // If prime[p] is not changed // then it is a prime if ( prime [ p ] == true ) { // Update all multiples of p for ( int i = p * 2 ; i <= n ; i += p ) prime [ i ] = false ; } } } // Function to generate mersenne // primes lessthan or equal to n static void mersennePrimes ( int n ) { // Create a boolean array // 'prime[0..n]' boolean prime []= new boolean [ n + 1 ] ; // Generating primes // using Sieve SieveOfEratosthenes ( n prime ); // Generate all numbers of // the form 2^k - 1 and // smaller than or equal to n. for ( int k = 2 ; (( 1 < < k ) - 1 ) <= n ; k ++ ) { long num = ( 1 < < k ) - 1 ; // Checking whether number is // prime and is one less than // the power of 2 if ( prime [ ( int )( num ) ] ) System . out . print ( num + ' ' ); } } // Driven program public static void main ( String args [] ) { int n = 31 ; System . out . println ( 'Mersenne prime' + 'numbers smaller than' + 'or equal to ' + n ); mersennePrimes ( n ); } } // This code is contributed by Nikita Tiwari.C## Program to generate mersenne primes # Generate all prime numbers # less than n. def SieveOfEratosthenes ( n prime ): # 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] for i in range ( 0 n + 1 ) : prime [ i ] = True p = 2 while ( p * p <= n ): # If prime[p] is not changed # then it is a prime if ( prime [ p ] == True ) : # Update all multiples of p for i in range ( p * 2 n + 1 p ): prime [ i ] = False p += 1 # Function to generate mersenne # primes less than or equal to n def mersennePrimes ( n ) : # Create a boolean array # 'prime[0..n]' prime = [ 0 ] * ( n + 1 ) # Generating primes using Sieve SieveOfEratosthenes ( n prime ) # Generate all numbers of the # form 2^k - 1 and smaller # than or equal to n. k = 2 while ((( 1 < < k ) - 1 ) <= n ): num = ( 1 < < k ) - 1 # Checking whether number # is prime and is one # less than the power of 2 if ( prime [ num ]) : print ( num end = ' ' ) k += 1 # Driver Code n = 31 print ( 'Mersenne prime numbers smaller' 'than or equal to ' n ) mersennePrimes ( n ) # This code is contributed # by SmithaJavaScript// C# Program to generate mersenne primes using System ; class GFG { // Generate all prime numbers less than n. static void SieveOfEratosthenes ( int n bool [] prime ) { // 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]; for ( int i = 0 ; i <= n ; i ++ ) prime [ i ] = true ; for ( int p = 2 ; p * p <= n ; p ++ ) { // If prime[p] is not changed // then it is a prime if ( prime [ p ] == true ) { // Update all multiples of p for ( int i = p * 2 ; i <= n ; i += p ) prime [ i ] = false ; } } } // Function to generate mersenne // primes lessthan or equal to n static void mersennePrimes ( int n ) { // Create a boolean array // 'prime[0..n]' bool [] prime = new bool [ n + 1 ]; // Generating primes // using Sieve SieveOfEratosthenes ( n prime ); // Generate all numbers of // the form 2^k - 1 and // smaller than or equal to n. for ( int k = 2 ; (( 1 < < k ) - 1 ) <= n ; k ++ ) { long num = ( 1 < < k ) - 1 ; // Checking whether number is // prime and is one less than // the power of 2 if ( prime [( int )( num )]) Console . Write ( num + ' ' ); } } // Driven program public static void Main () { int n = 31 ; Console . WriteLine ( 'Mersenne prime numbers' + ' smaller than or equal to ' + n ); mersennePrimes ( n ); } } // This code is contributed by nitin mittal.PHP< script > // JavaScript to generate // mersenne primes // Generate all prime numbers // less than n. function SieveOfEratosthenes ( n prime ) { // 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]; for ( let i = 0 ; i <= n ; i ++ ) prime [ i ] = true ; for ( let p = 2 ; p * p <= n ; p ++ ) { // If prime[p] is not changed // then it is a prime if ( prime [ p ] == true ) { // Update all multiples of p for ( let i = p * 2 ; i <= n ; i += p ) prime [ i ] = false ; } } } // Function to generate mersenne // primes lessthan or equal to n function mersennePrimes ( n ) { // Create a boolean array // 'prime[0..n]' let prime = []; // Generating primes // using Sieve SieveOfEratosthenes ( n prime ); // Generate all numbers of // the form 2^k - 1 and // smaller than or equal to n. for ( let k = 2 ; (( 1 < < k ) - 1 ) <= n ; k ++ ) { let num = ( 1 < < k ) - 1 ; // Checking whether number is // prime and is one less than // the power of 2 if ( prime [( num )]) document . write ( num + ' ' ); } } // Driver Code let n = 31 ; document . write ( 'Mersenne prime' + 'numbers smaller than' + 'or equal to ' + n + '
' ); mersennePrimes ( n ); // This code is contributed by code_hunt. < /script>Lähtö:
Mersenne prime numbers smaller than or equal to 31
3 7 31Aika monimutkaisuus: O (n*log(logn))
Avaruuden monimutkaisuus: O(N)
Luo tietokilpailu
Viitteet:
https://en.wikipedia.org/wiki/Mersenne_prime
