Рубрики

Софи Жермен Прайм

Напишите программу для печати всех номеров sophie germain меньше n. Простое число p называется простым числом софи, если 2p + 1 также является простым числом. Число 2p + 1 называется безопасным простым числом. Например, 11 — простое число, а 11 * 2 + 1 = 23 — также простое число, поэтому 11 — простое число sophie germain. Первые несколько простых чисел Софи Германии: 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179 ..

Примеры:

Input : 25
Output : 2 3 5 11 23

Вот программа для печати номера софье Жермена ниже n.
Решение этого просто. Чтобы получить все числа Софи ниже n, мы сделаем цикл до n, и для каждого числа в цикле мы можем проверить, что это число и (2 * число + 1) , оба простые или нет, и для проверки этого мы использовали Сито из метода Эрастотен .

Ниже приведена реализация этого подхода.

C ++

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

using namespace std;

  
// функция для определения простого числа
// здесь мы использовали метод сита
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/amp/
// определить простое число

bool sieve(int n, bool prime[])

{

    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;

        }

    }

}

  

void printSophieGermanNumber(int n)

{

    // мы сделали массив до 2 * n +1

    // чтобы мы могли проверить простое число

    // до этого и сделаем вывод о софи

    // немецкий премьер.

    bool prime[2 * n + 1];

    memset(prime, true, sizeof(prime));

    sieve(2 * n + 1, prime);

  

    for (int i = 2; i <= n; ++i) {

  

        // проверяем каждый ли он

        // Софи немецкий премьер или нет.

        if (prime[i] && prime[2 * i + 1]) 

            cout << i << " ";        

    }

}

  

int main()

{

    int n = 25;

    printSophieGermanNumber(n);

    return 0;

}

Джава

// Java-программа для печати всех
// Софи немецкое простое число до n.

import java.io.*;

import java.util.*;

      

class GFG {

      

    // функция для определения простого числа

    // здесь мы использовали метод сита

    // https://www.geeksforgeeks.org/sieve-of-eratosthenes/amp/

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

    static void sieve(int n, boolean prime[])

    {

        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;

            }

        }

    }

      

    static void printSophieGermanNumber(int n)

    {

        // мы сделали массив до 2 * n +1

        // чтобы мы могли проверить простое число

        // до этого и сделаем вывод о софи

        // немецкий премьер.

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

        Arrays.fill(prime,true);

        sieve(2 * n + 1, prime);

      

        for (int i = 2; i < n; ++i) {

      

            // проверяем каждый ли он

            // Софи немецкий премьер или нет.

            if (prime[i] && prime[2 * i + 1]) 

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

        }

    }

      

    public static void main(String args[])

    {

        int n = 25;

        printSophieGermanNumber(n);

    }

}

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

python3

# Python 3 программа для печати всех софи
# немецкое простое число до n.

  
# Функция для определения простого числа
# здесь мы использовали метод сита
# https://www.geeksforgeeks.org/sieve-of-eratosthenes/amp/
# для определения простого числа

def sieve(n, prime) :

    p = 2

    while( p * p <= n ):

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

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

        if (prime[p] == True) :

              

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

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

                prime[i] = False

                  

        p += 1

          

                  

def printSophieGermanNumber(n) :

    # Мы сделали массив до 2 * n +1

    # чтобы мы могли проверить простое число

    # до этого и сделать вывод о Софи

    # немецкий премьер.

    prime = [True]*(2 * n + 1)

      

    sieve(2 * n + 1, prime)

  

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

          

        # проверять каждый ли я

        # Софи немецкий премьер или нет.

        if (prime[i] and prime[2 * i + 1]) :

            print( i , end = " ")

              

  
Код водителя

n = 25

printSophieGermanNumber(n)

  

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

C #

// C # программа для печати
// все софи немецкое
// простое число до n.

using System;

      

class GFG

{

      

    // функция для обнаружения простого числа

    // номер здесь мы использовали

    // метод сита

    // https://www.geeksforgeeks.org/sieve-of-eratosthenes/amp/

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

    static void sieve(int n,

                      bool []prime)

    {

        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;

            }

        }

    }

      

    static void printSophieGermanNumber(int n)

    {

        // мы сделали массив до

        // 2 * n +1, чтобы мы могли

        // проверяем простое число до

        // это и вывод о

        // Софи немецкий премьер.

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

        for (int i = 0; 

                 i < prime.Length; i++)

        {

            prime[i] = true;

        }

        sieve(2 * n + 1, prime);

      

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

        {

      

            // проверяем каждый ли

            // это софи немецкий премьер

            // или не.

            if (prime[i] && prime[2 * i + 1]) 

                Console.Write( i + " ");     

        }

    }     

      

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

    static void Main()

    {

        int n = 25;

        printSophieGermanNumber(n);

    }

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)

PHP

<?php
// PHP программа для печати
// все софи немецкое
// простое число до n.

  
// функция для обнаружения простого числа
// номер здесь мы использовали
// метод сита
// https://www.geeksforgeeks.org/sieve-of-eratosthenes/amp/
// определить простое число

function sieve($n, &$prime)

{

    for ($p = 2; 

         $p * $p <= $n; $p++) 

    {

  

        // Если простое число [p]

        // то не изменилось

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

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

        {

  

            // Обновить все

            // кратно p

            for ($i = $p * 2;

                 $i <= $n; $i += $p)

                $prime[$i] = false;

        }

    }

}

  

function printSophieGermanNumber($n)

{

    // мы сделали массив до

    // 2 * n +1, чтобы мы могли

    // проверяем простое число до

    // это и вывод о

    // Софи немецкий премьер.

    $prime = array();

    for($i = 0; 

        $i < (2 * $n + 1); $i++)

        $prime[$i] = true;

  

    sieve(2 * $n + 1, $prime);

  

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

    {

  

        // проверяем каждый я

        // это софи

        // немецкий премьер или нет.

        if ($prime[$i] &&

            $prime[2 * $i + 1]) 

            echo ($i . " ");     

    }

}

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

$n = 25;

printSophieGermanNumber($n);

  
// Этот код предоставлен
// Маниш Шоу (manishshaw1)
?>


Выход :

2 3 5 11 23

Применение Софи простых чисел:

1. It is used in cryptography as safe primes become the factors of a secret key in RSA cryptosystem.
2. In the first version of AKS Primality Test, it is used to lower the worst case complexity .
3. It is used in the generation of Pseudo Random Number .

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

Софи Жермен Прайм

0.00 (0%) 0 votes