Mersenne Prime es un número primo que es uno menos que una potencia de dos. En otras palabras, cualquier número primo es Mersenne Prime si tiene la forma 2 k -1, donde k es un número entero mayor o igual que 2. Los primeros números primos de Mersenne son 3, 7, 31 y 127.
La tarea es imprimir todos los números primos de Mersenne . Primos más pequeños que un entero positivo de entrada n.
Ejemplos:
Input: 10 Output: 3 7 3 and 7 are prime numbers smaller than or equal to 10 and are of the form 2k-1 Input: 100 Output: 3 7 31
La idea es generar todos los números primos menores o iguales al número dado n usando la Criba de Eratóstenes . Una vez que hemos generado todos esos primos, iteramos a través de todos los números de la forma 2 k -1 y comprobamos si son primos o no.
A continuación se muestra la implementación de la idea.
C++
// Program to generate mersenne primes #include<bits/stdc++.h> using 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; }
Java
// 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.
Python3
# 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 Smitha
C#
// 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
<?php // Program to generate mersenne primes // Generate all prime numbers less than n. function SieveOf($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 $prime = array($n + 1); for ($i = 0; $i <= $n; $i++) $prime[$i] = true; for ($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 ($i = $p * 2; $i <= $n; $i += $p) $prime[$i] = false; } } return $prime; } // Function to generate mersenne // primes less than or equal to n function mersennePrimes($n) { // Create a boolean array "prime[0..n]" // bool prime[n+1]; // Generating primes using Sieve $prime = SieveOf($n); // Generate all numbers of the // form 2^k - 1 and smaller // than or equal to n. for ($k = 2; ((1 << $k) - 1) <= $n; $k++) { $num = (1 << $k) - 1; // Checking whether number is prime // and is one less then the power of 2 if ($prime[$num]) echo $num . " "; } } // Driver Code $n = 31; echo "Mersenne prime numbers smaller " . "than or equal to $n " . mersennePrimes($n); // This code is contributed by mits ?>
Javascript
<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 then // 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 + "<br/>"); mersennePrimes(n); // This code is contributed by code_hunt. </script>
Producción:
Mersenne prime numbers smaller than or equal to 31 3 7 31
Complejidad de tiempo: O (n*log(logn))
Complejidad espacial : O(N)
Referencias:
https://en.wikipedia.org/wiki/Mersenne_prime
Este artículo es una contribución de Rahul Agrawal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA