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