Mersenne primer

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *