Рубрики

Подсчитать пары с суммой в качестве простого числа и меньше чем n

Учитывая положительное целое число n, подсчитайте различное количество пар (x, y), которые удовлетворяют следующим условиям:

  • (x + y) простое число.
  • (x + y) <n
  • х! = у
  • 1 <= х, у

Примеры:

Input : n = 6
Output : 3
prime pairs whose sum is less than 6 are:
(1,2), (1,4), (2,3) 

Input : 12
Output : 11
prime pairs whose sum is less than 12 are:
(1,2),  (1,4), (2,3), (1,6), (2,5), (3,4), 
(1,10), (2,9), (3,8), (4,7), (5,6)

Подходить:

1) Find all prime numbers less than n using
   Sieve of Sundaram

2) For each prime number p, count distinct
   pairs that sum up to p.
   
For any odd number n, number of distinct pairs
that add upto n are n/2
Since, a prime number is a odd number, the 
same applies for it too. 

Пример,
Для простого числа p = 7
отдельные пары, которые складываются в p: p / 2 = 7/2 = 3
Три пары (1,6), (2,5), (3,4)

Для простого числа р = 23
отдельные пары, которые складываются в p: p / 2 = 23/2 = 11

C ++

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

using namespace std;

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

void SieveOfSundaram(bool marked[], int nNew)

{

    // Основная логика сундарама. Отметить все номера

    // в форме i + j + 2ij, где true, где

    // 1 <= i <= j

    for (int i=1; i<=nNew; i++)

        for (int j=i; (i + j + 2*i*j) <= nNew; j++)

            marked[i + j + 2*i*j] = true;

}

  
// Возвращает количество пар с пятью условиями.

int countPrimePairs(int n)

{

    // В общем сито сундарам, производит

    // простые числа меньше (2 * x + 2) для числа

    // заданное число х. Так как мы хотим, чтобы простые числа были меньше

    // чем n, мы уменьшаем n до половины

    int nNew = (n-2)/2;

  

    // Этот массив используется для разделения чисел

    // форма i + j + 2ij от других где

    // 1 <= i <= j

    bool marked[nNew + 1];

  

    // Инициализируем все элементы как не отмеченные

    memset(marked, false, sizeof(marked));

  

    SieveOfSundaram(marked, nNew);

  

    int count = 0, prime_num;

  

    // Найти простые числа. Простые числа имеют форму

    // 2 * i + 1 такой, что отмеченный [i] является ложным.

    for (int i=1; i<=nNew; i++)

    {

        if (marked[i] == false)

        {

            prime_num = 2*i + 1;

  

            // Для заданного простого числа p

            // количество различных пар (i, j)

            // где (i + j) = p - p / 2

            count = count + (prime_num / 2);

        }

    }

  

    return count;

}

  
// Программа драйвера для тестирования выше

int main(void)

{

    int n = 12;

    cout << "Number of prime pairs: "

         << countPrimePairs(n);

    return 0;

}

Джава

// Java реализация простых пар
// чья сумма меньше n

  

class GFG

{

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

static void SieveOfSundaram(boolean marked[], int nNew) 

      

    // Основная логика сундарама. Отметить все номера

    // в форме i + j + 2ij, где true, где

    // 1 <= i <= j

    for (int i = 1; i <= nNew; i++) 

        for (int j = i; (i + j + 2 * i * j) <= nNew; j++) 

            marked[i + j + 2 * i * j] = true

  
// Возвращает количество пар с пятью условиями.

static int countPrimePairs(int n) 

    // В общем сито сундарам, производит

    // простые числа меньше (2 * x + 2) для числа

    // заданное число х. Так как мы хотим, чтобы простые числа были меньше

    // чем n, мы уменьшаем n до половины

    int nNew = (n - 2) / 2

  

    // Этот массив используется для разделения чисел

    // форма i + j + 2ij от других где

    // 1 <= i <= j

    // Инициализируем все элементы как не отмеченные

    boolean marked[]=new boolean[nNew + 1]; 

  

    SieveOfSundaram(marked, nNew);

    int count = 0, prime_num; 

  

    // Найти простые числа. Простые числа имеют форму

    // 2 * i + 1 такой, что отмеченный [i] является ложным.

    for (int i = 1; i <= nNew; i++) 

    

        if (marked[i] == false

        

            prime_num = 2 * i + 1

  

            // Для заданного простого числа p

            // количество различных пар (i, j)

            // где (i + j) = p - p / 2

            count = count + (prime_num / 2); 

        

    

    return count; 

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

public static void main (String[] args) 

{

    int n = 12

    System.out.println("Number of prime pairs: " +

    countPrimePairs(n)); 


}

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

python3

# Python3 реализация простых пар
# чья сумма меньше чем n

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

def SieveOfSundaram(marked, nNew):

      

    # Основная логика Сундарама. Отметить все номера

    # формы i + j + 2ij как истина где

    # 1 <= i <= j

    for i in range(1, nNew + 1):

        for j in range(i, nNew):

            if i + j + 2 * i * j > nNew:

                break

            marked[i + j + 2 * i * j] = True

  
# Возвращает количество пар с пятью условиями.

def countPrimePairs(n):

      

    # В общем Сито Сундарам, производит

    # простых чисел меньше (2 * x + 2) для числа

    # данное число х. Так как мы хотим, чтобы простые числа были меньше

    # чем n, мы уменьшаем n до половины

    nNew = (n - 2) // 2

  

    # Этот массив используется для разделения чисел

    # вида i + j + 2ij от других, где

    # 1 <= i <= j

    marked = [ False for i in range(nNew + 1)]

  

    SieveOfSundaram(marked, nNew)

  

    count, prime_num = 0, 0

  

    # Найти простые числа. Простые числа имеют форму

    # 2 * i + 1 такой, что помеченный [i] является ложным.

    for i in range(1, nNew + 1):

        if (marked[i] == False):

  

            prime_num = 2 * i + 1

  

            # Для заданного простого числа p

            # количество различных пар (i, j)

            # где (i + j) = p - p / 2

            count = count + (prime_num // 2)

  

    return count

  
Код водителя

n = 12

print("Number of prime pairs: "

             countPrimePairs(n))

  
# Этот код предоставлен Мохитом Кумаром 29

C #

// C # реализация простых пар
// чья сумма меньше n

using System;

  

class GFG

{

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

static void SieveOfSundaram(bool[] marked, 

                            int nNew) 

      

    // Основная логика сундарама. Отметить все номера

    // в форме i + j + 2ij, где true, где

    // 1 <= i <= j

    for (int i = 1; i <= nNew; i++) 

        for (int j = i; 

            (i + j + 2 * i * j) <= nNew; j++) 

            marked[i + j + 2 * i * j] = true

  
// Возвращает количество пар с пятью условиями.

static int countPrimePairs(int n) 

    // В общем сито сундарам, производит

    // простые числа меньше (2 * x + 2) для

    // номер заданный номер x. Так как мы хотим

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

    int nNew = (n - 2) / 2; 

  

    // Этот массив используется для разделения чисел

    // вида i + j + 2ij от других, где

    // 1 <= i <= j

    // Инициализируем все элементы как не отмеченные

    bool[] marked = new bool[nNew + 1]; 

  

    SieveOfSundaram(marked, nNew);

    int count = 0, prime_num; 

  

    // Найти простые числа. Простые числа имеют форму

    // 2 * i + 1 такой, что отмеченный [i] является ложным.

    for (int i = 1; i <= nNew; i++) 

    

        if (marked[i] == false

        

            prime_num = 2 * i + 1; 

  

            // Для заданного простого числа p

            // количество различных пар (i, j)

            // где (i + j) = p - p / 2

            count = count + (prime_num / 2); 

        

    

    return count; 

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

public static void Main () 

{

    int n = 12; 

    Console.WriteLine("Number of prime pairs: "

                             countPrimePairs(n)); 


}

  
// Этот код предоставлен Мукулом Сингхом.

PHP

<?php
// PHP реализация простых пар
// чья сумма меньше n

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

function SieveOfSundaram(&$marked, $nNew)

{

    // Основная логика сундарама. пометить все

    // числа вида i + j + 2ij

    // как истина, где 1 <= i <= j

    for ($i = 1; $i <= $nNew; $i++)

        for ($j = $i

            ($i + $j + 2 * $i * $j) <= $nNew; $j++)

            $marked[$i + $j + 2 * $i * $j] = true;

}

  
// Возвращает количество пар с
// заданные условия.

function countPrimePairs($n)

{

    // В общем сито сундарам, производит

    // простые числа меньше (2 * x + 2) для

    // номер заданный номер x. Так как мы хотим

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

    $nNew = ($n - 2) / 2;

  

    // Этот массив используется для разделения чисел

    // вида i + j + 2ij от других, где

    // 1 <= i <= j

    $marked = array_fill(0, $nNew + 1, false);

  

    SieveOfSundaram($marked, $nNew);

  

    $count = 0;

  

    // Найти простые числа. Простые числа имеют форму

    // 2 * i + 1 такой, что отмеченный [i] является ложным.

    for ($i = 1; $i <= $nNew; $i++)

    {

        if ($marked[$i] == false)

        {

            $prime_num = 2 * $i + 1;

  

            // Для заданного простого числа p

            // количество различных пар (i, j)

            // где (i + j) = p - p / 2

            $count = $count + (int)($prime_num / 2);

        }

    }

  

    return $count;

}

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

$n = 12;

echo "Number of prime pairs: "

            countPrimePairs($n);

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


Выход:

Number of prime pairs: 11

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

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

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

Подсчитать пары с суммой в качестве простого числа и меньше чем n

0.00 (0%) 0 votes