Рубрики

Найти два простых числа с заданной суммой

Если задано четное число (больше 2), выведите два простых числа, сумма которых будет равна данному числу. Возможны несколько комбинаций. Напечатайте только первую такую пару.

Интересно, что решение всегда существует в соответствии с гипотезой Гольдбаха .

Примеры :

Input: n = 74
Output: 3 71

Input : n = 1024
Output: 3 1021

Input: n = 66
Output: 5 61

Input: n = 9990
Output: 17 9973

Идея состоит в том, чтобы найти все простые числа, меньшие или равные данному числу N, используя Сито Эратосфена. Как только у нас есть массив, который сообщает все простые числа, мы можем пройти через этот массив, чтобы найти пару с заданной суммой.

C ++

// C ++ программа для поиска пары простых чисел,
// сумма равна заданному числу
// C ++ программа для печати супер простых чисел меньше
// или равно n.
#include<bits/stdc++.h>

using namespace std;

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

bool SieveOfEratosthenes(int n, bool isPrime[])

{

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

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

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

    // bool isPrime [n + 1];

    isPrime[0] = isPrime[1] = false;

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

        isPrime[i] = true;

  

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

    {

        // Если isPrime [p] не изменился, то это

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

        if (isPrime[p] == true)

        {

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

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

                isPrime[i] = false;

        }

    }

}

  
// Печатает пару простых чисел с заданной суммой

void findPrimePair(int n)

{

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

    bool isPrime[n+1];

    SieveOfEratosthenes(n, isPrime);

  

    // Обходим все числа, чтобы найти первыми

    // пара

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

    {

        if (isPrime[i] && isPrime[n-i])

        {

            cout << i << " " << (n-i);

            return;

        }

    }

}

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

int main()

{

    int n = 74;

    findPrimePair(n);

    return 0;

}

Джава

// Java-программа для поиска пары простых чисел,
// сумма равна заданному числу
// Java-программа для печати супер простых чисел меньше
// или равно n.

  

class GFG

{

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

    static boolean SieveOfEratosthenes(int n, boolean isPrime[])

    {

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

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

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

        // простое, иначе true bool isPrime [n + 1];

        isPrime[0] = isPrime[1] = false;

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

            isPrime[i] = true;

      

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

        {

            // Если isPrime [p] не изменился,

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

            if (isPrime[p] == true)

            {

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

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

                    isPrime[i] = false;

            }

        }

        return false;

    }

      

    // Печатает пару простых чисел с заданной суммой

    static void findPrimePair(int n)

    {

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

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

        SieveOfEratosthenes(n, isPrime);

      

        // Обходим все числа, чтобы найти первыми

        // пара

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

        {

            if (isPrime[i] && isPrime[n - i])

            {

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

                return;

            }

        }

    }

      

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

    public static void main (String[] args)

    {

        int n = 74;

        findPrimePair(n);

    }

}

  
// Этот код предоставлен Anant Agarwal.

Python 3

# Программа Python 3 для поиска простого числа
# пара, сумма которой равна заданному числу
# Программа Python 3 для печати супер простых чисел
# меньше или равно n.

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

def SieveOfEratosthenes(n, isPrime):

  

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

    # массив как True. Значение в isPrime [i]

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

    # prime, иначе True bool isPrime [n + 1]

    isPrime[0] = isPrime[1] = False

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

        isPrime[i] = True

  

    p = 2

    while(p*p <= n):

      

        # Если isPrime [p] не изменяется,

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

        if (isPrime[p] == True):

          

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

            i = p*p

            while(i <= n):

                isPrime[i] = False

                i += p

        p += 1

          
# Печатает простую пару с заданной суммой

def findPrimePair(n):

  

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

    isPrime = [0] * (n+1)

    SieveOfEratosthenes(n, isPrime)

  

    # Обход всех номеров, чтобы найти

    # первая пара

    for i in range(0, n):

      

        if (isPrime[i] and isPrime[n - i]):

          

            print(i,(n - i))

            return

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

n = 74

findPrimePair(n)

  
# Этот код предоставлен
# Смита Динеш Семвал

C #

// C # программа для поиска пары простых чисел,
// сумма равна заданному числу
// C # программа для печати супер простых чисел меньше
// или равно n.

using System;

  

class GFG

{

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

    static bool SieveOfEratosthenes(int n, bool []isPrime)

    {

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

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

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

        // простое, иначе true bool isPrime [n + 1];

        isPrime[0] = isPrime[1] = false;

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

            isPrime[i] = true;

      

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

        {

            // Если isPrime [p] не изменился,

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

            if (isPrime[p] == true)

            {

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

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

                    isPrime[i] = false;

            }

        }

        return false;

    }

      

    // Печатает пару простых чисел с заданной суммой

    static void findPrimePair(int n)

    {

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

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

        SieveOfEratosthenes(n, isPrime);

      

        // Обходим все числа, чтобы найти первыми

        // пара

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

        {

            if (isPrime[i] && isPrime[n - i])

            {

                Console.Write(i + " " + (n - i));

                return;

            }

        }

    }

      

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

    public static void Main ()

    {

        int n = 74;

        findPrimePair(n);

    }

}

  
// Этот код предоставлен vt_m.

PHP

<?php 
// PHP программа для поиска простого числа
// номер пары, чья сумма равна
// на указанный номер

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

function SieveOfEratosthenes($n, &$isPrime)

{

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

    // логический массив как true. Ценность

    // в isPrime [i] будет наконец

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

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

    $isPrime[0] = $isPrime[1] = false;

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

        $isPrime[$i] = true;

  

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

    {

        // Если isPrime [p] не изменился,

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

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

        {

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

            for ($i = $p * $p

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

                $isPrime[$i] = false;

        }

    }

}

  
// Печатает пару простых чисел с заданной суммой

function findPrimePair($n)

{

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

    $isPrime = array_fill(0, $n + 1, NULL);

    SieveOfEratosthenes($n, $isPrime);

  

    // Обход всех чисел

    // найти первую пару

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

    {

        if ($isPrime[$i] && 

            $isPrime[$n - $i])

        {

            echo $i . " " . ($n - $i);

            return;

        }

    }

}

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

$n = 74;

findPrimePair($n);

  
// Этот код добавлен
// ChitraNayal
?>



Выход:

3 71

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

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

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

Найти два простых числа с заданной суммой

0.00 (0%) 0 votes