Рубрики

Мерсенн Прайм

Мерсенн Прайм — это простое число, которое на единицу меньше степени двух. Другими словами, любое простое число — это простое число Мерсенна, если оно имеет форму 2 k -1, где k — целое число, большее или равное 2. Первые несколько простых чисел Мерсенна равны 3, 7, 31 и 127.

Задача — вывести все простые числа Мерсенна меньше, чем входное положительное целое число n.

Примеры:

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 

Идея состоит в том, чтобы сгенерировать все простые числа, меньшие или равные данному числу n, используя Сито Эратосфена . После того как мы сгенерировали все такие простые числа, мы перебираем все числа в форме 2 k -1 и проверяем, являются ли они простыми числами или нет.

Ниже приведена реализация идеи.

C ++

// Программа для генерации простых чисел Мерсенна
#include<bits/stdc++.h>

using namespace std;

  
// Генерируем все простые числа меньше n.

void SieveOfEratosthenes(int n, bool prime[])

{

    // Инициализируем все записи логического массива

    // как правда. Значение в простом [i] будет, наконец,

    // быть ложным, если я не простое, иначе верно

    // bool prime [n + 1];

    for (int i=0; i<=n; i++)

        prime[i] = true;

  

    for (int p=2; p*p<=n; p++)

    {

        // Если простое число [p] не изменилось, то оно

        // простое число

        if (prime[p] == true)

        {

            // Обновить все кратные р

            for (int i=p*2; i<=n; i += p)

                prime[i] = false;

        }

    }

}

  
// Функция для генерации простых чисел Мерсенна
// чем или равно n

void mersennePrimes(int n)

{

    // Создаем логический массив "prime [0..n]"

    bool prime[n+1];

  

    // Генерация простых чисел с использованием Sieve

    SieveOfEratosthenes(n,prime);

  

    // Генерируем все числа вида 2 ^ k - 1

    // и меньше или равно n.

    for (int k=2; ((1<<k)-1) <= n; k++)

    {

        long long num = (1<<k) - 1;

  

        // Проверка, является ли число простым и

        // на единицу меньше, чем степень 2

        if (prime[num])

            cout << num << " ";

    }

}

  
// Управляемая программа

int main()

{

    int n = 31;

    cout << "Mersenne prime numbers smaller "

         << "than or equal to " << n << endl;

    mersennePrimes(n);

    return 0;

}

Джава

// Программа для генерации
// простые числа Мерсенна

import java.io.*;

  

class GFG {

      

    // Генерируем все простые числа

    // меньше чем n.

    static void SieveOfEratosthenes(int n,

                          boolean prime[])

    {

        // Инициализируем все записи

        // логический массив как true.

        // значение в простом [i] будет наконец

        // быть ложным, если я не простое число,

        // иначе true bool prime [n + 1];

        for (int i = 0; i <= n; i++)

            prime[i] = true;

      

        for (int p = 2; p * p <= n; p++)

        {

            // Если простое число [p] не изменилось

            // тогда это простое число

            if (prime[p] == true)

            {

                // Обновить все кратные р

                for (int i = p * 2; i <= n; i += p)

                    prime[i] = false;

            }

        }

    }

      

    // Функция для генерации мерсенна

    // простое число меньше или равно n

    static void mersennePrimes(int n)

    {

        // Создать логический массив

        // "prime [0..n]"

        boolean prime[]=new boolean[n + 1];

      

        // Генерация простых чисел

        // используя сито

        SieveOfEratosthenes(n, prime);

      

        // Генерируем все числа

        // форма 2 ^ k - 1 и

        // меньше или равно n.

        for (int k = 2; (( 1 << k) - 1) <= n; k++)

        {

            long num = ( 1 << k) - 1;

      

            // Проверка, является ли число

            // простое число на единицу меньше

            // сила 2

            if (prime[(int)(num)])

                System.out.print(num + " ");

        }

    }

      

    // Управляемая программа

    public static void main(String args[])

    {

        int n = 31;

        System.out.println("Mersenne prime"+

                     "numbers smaller than"+

                          "or equal to "+n);

          

        mersennePrimes(n);

    }

}

  
// Этот код предоставлен Никитой Тивари.

python3

# Программа для генерации простых чисел Мерсенна

  
# Генерация всех простых чисел
# меньше чем n.

def SieveOfEratosthenes(n, prime): 

  

    # Инициализировать все записи логического

    # массив как истина. Значение в простом [i]

    # наконец будет ложным, если я не

    # простое, иначе истинное bool prime [n + 1]

    for i in range(0, n + 1) :

        prime[i] = True

  

    p = 2

    while(p * p <= n):

      

        # Если простое число [p] не изменилось,

        # тогда это простое

        if (prime[p] == True) :

          

            # Обновить все кратные р

            for i in range(p * 2, n + 1, p):

                prime[i] = False

                  

        p += 1

          
# Функция для генерации мерсенна
# простых чисел меньше или равно n

def mersennePrimes(n) :

  

    # Создать логический массив

    # "prime [0..n]"

    prime = [0] * (n + 1)

  

    # Генерация простых чисел с помощью Sieve

    SieveOfEratosthenes(n, prime) 

  

    # Генерация всех чисел

    # форма 2 ^ k - 1 и меньше

    # чем или равно n.

    k = 2

    while(((1 << k) - 1) <= n ):

      

        num = (1 << k) - 1

  

        # Проверка номера

        # простое и одно

        # меньше силы 2

        if (prime[num]) :

            print(num, end = " " )

              

        k += 1

      
Код водителя

n = 31

print("Mersenne prime numbers smaller"

              "than or equal to " , n ) 

mersennePrimes(n) 

  
# Этот код добавлен
# от Smitha

C #

// C # Программа для генерации простых чисел Мерсенна

using System;

  

class GFG {

      

    // Генерируем все простые числа меньше n.

    static void SieveOfEratosthenes(int n,

                                bool []prime)

    {

          

        // Инициализируем все записи

        // логический массив как true.

        // значение в простом [i] будет наконец

        // быть ложным, если я не простое число,

        // иначе true bool prime [n + 1];

        for (int i = 0; i <= n; i++)

            prime[i] = true;

      

        for (int p = 2; p * p <= n; p++)

        {

              

            // Если простое число [p] не изменилось,

            // тогда это простое число

            if (prime[p] == true)

            {

                  

                // Обновить все кратные р

                for (int i = p * 2; i <= n; i += p)

                    prime[i] = false;

            }

        }

    }

      

    // Функция для генерации мерсенна

    // простое число меньше или равно n

    static void mersennePrimes(int n)

    {

          

        // Создать логический массив

        // "prime [0..n]"

        bool []prime = new bool[n + 1];

      

        // Генерация простых чисел

        // используя сито

        SieveOfEratosthenes(n, prime);

      

        // Генерируем все числа

        // форма 2 ^ k - 1 и

        // меньше или равно n.

        for (int k = 2; (( 1 << k) - 1) <= n; k++)

        {

            long num = ( 1 << k) - 1;

      

            // Проверка, является ли число

            // простое число на единицу меньше

            // сила 2

            if (prime[(int)(num)])

                Console.Write(num + " ");

        }

    }

      

    // Управляемая программа

    public static void Main()

    {

        int n = 31;

          

        Console.WriteLine("Mersenne prime numbers"

               + " smaller than or equal to " + n);

          

        mersennePrimes(n);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Программа для генерации простых чисел Мерсенна

  
// Генерируем все простые числа меньше n.

function SieveOf($n)

{

    // Инициализируем все записи логического

    // массив как истина. Значение в простом [i]

    // будет, наконец, ложным, если я не

    // простое число, иначе верно

    $prime = array($n + 1);

    for ($i = 0; $i <= $n; $i++)

        $prime[$i] = true;

  

    for ($p = 2; $p * $p <= $n; $p++)

    {

        // Если простое число [p] не изменилось,

        // тогда это простое число

        if ($prime[$p] == true)

        {

            // Обновить все кратные р

            for ($i = $p * 2; $i <= $n; $i += $p)

                $prime[$i] = false;

        }

    }

    return $prime;

}

  
// Функция для генерации мерсенна
// простые числа, меньшие или равные n

function mersennePrimes($n)

{

    // Создаем логический массив "prime [0..n]"

    // bool prime [n + 1];

  

    // Генерация простых чисел с использованием Sieve

    $prime = SieveOf($n);

  

    // Генерируем все числа

    // форма 2 ^ k - 1 и меньше

    // чем или равно n.

    for ($k = 2; ((1 << $k) - 1) <= $n; $k++)

    {

        $num = (1 << $k) - 1;

  

        // Проверка, является ли число простым

        // и на единицу меньше степени 2

        if ($prime[$num])

            echo $num . " ";

  

    }

}

  
// Код драйвера

$n = 31;

echo "Mersenne prime numbers smaller "

     "than or equal to $n "

      mersennePrimes($n);

  
// Этот код предоставлен mits
?>


Выход:

Mersenne prime numbers smaller than or equal to 31
3 7 31 

Ссылки:
https://en.wikipedia.org/wiki/Mersenne_prime

Эта статья предоставлена Рахул Агравал . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Мерсенн Прайм

0.00 (0%) 0 votes