Contar pares con suma como número primo y menor que n

Dado un entero positivo n, cuente un número distinto de pares (x, y) que satisfagan las siguientes condiciones: 

• (x + y) es un número primo.
• (x + y) < norte
• x != y
• 1 <= x, y

Ejemplos: 

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)

Acercarse: 

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. 

Ejemplo, 
para el número primo p = 7 
pares distintos que suman p: p/2 = 7/2 = 3 
Los tres pares son (1,6), (2,5), (3,4)
Para el número primo p = 23 
pares distintos que suman p: p/2 = 23/2 = 11 
 

// C++ implementation of prime pairs
// whose sum is less than n
#include <bits/stdc++.h>
using namespace std;
 
// Sieve of Sundaram for generating
// prime numbers less than n
void SieveOfSundaram(bool marked[], int nNew)
{
    // Main logic of Sundaram.  Mark all numbers
    // of the form i + j + 2ij as true where
    // 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;
}
 
// Returns number of pairs with given conditions.
int countPrimePairs(int n)
{
    // In general Sieve of Sundaram, produces
    // primes smaller than (2*x + 2) for a number
    // given number x. Since we want primes smaller
    // than n, we reduce n to half
    int nNew = (n-2)/2;
 
    // This array is used to separate numbers of
    // the form i+j+2ij from others where
    // 1 <= i <= j
    bool marked[nNew + 1];
 
    // Initialize all elements as not marked
    memset(marked, false, sizeof(marked));
 
    SieveOfSundaram(marked, nNew);
 
    int count = 0, prime_num;
 
    // Find primes. Primes are of the form
    // 2*i + 1 such that marked[i] is false.
    for (int i=1; i<=nNew; i++)
    {
        if (marked[i] == false)
        {
            prime_num = 2*i + 1;
 
            // For a given prime number p
            // number of distinct pairs(i,j)
            // where (i+j) = p are p/2
            count = count + (prime_num / 2);
        }
    }
 
    return count;
}
 
// Driver program to test above
int main(void)
{
    int n = 12;
    cout << "Number of prime pairs: "
         << countPrimePairs(n);
    return 0;
}

// Java implementation of prime pairs
// whose sum is less than n
 
class GFG
{
     
// Sieve of Sundaram for generating
// prime numbers less than n
static void SieveOfSundaram(boolean marked[], int nNew)
{
     
    // Main logic of Sundaram. Mark all numbers
    // of the form i + j + 2ij as true where
    // 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;
}
 
// Returns number of pairs with given conditions.
static int countPrimePairs(int n)
{
    // In general Sieve of Sundaram, produces
    // primes smaller than (2*x + 2) for a number
    // given number x. Since we want primes smaller
    // than n, we reduce n to half
    int nNew = (n - 2) / 2;
 
    // This array is used to separate numbers of
    // the form i+j+2ij from others where
    // 1 <= i <= j
    // Initialize all elements as not marked
    boolean marked[]=new boolean[nNew + 1];
 
    SieveOfSundaram(marked, nNew);
    int count = 0, prime_num;
 
    // Find primes. Primes are of the form
    // 2*i + 1 such that marked[i] is false.
    for (int i = 1; i <= nNew; i++)
    {
        if (marked[i] == false)
        {
            prime_num = 2 * i + 1;
 
            // For a given prime number p
            // number of distinct pairs(i, j)
            // where (i + j) = p are p/2
            count = count + (prime_num / 2);
        }
    }
    return count;
}
 
// Driver code
public static void main (String[] args)
{
    int n = 12;
    System.out.println("Number of prime pairs: " +
    countPrimePairs(n));
}
}
 
// This code is contributed by mits

# Python3 implementation of prime pairs
# whose sum is less than n
 
# Sieve of Sundaram for generating
# prime numbers less than n
def SieveOfSundaram(marked, nNew):
     
    # Main logic of Sundaram. Mark all numbers
    # of the form i + j + 2ij as true where
    # 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
 
# Returns number of pairs with given conditions.
def countPrimePairs(n):
     
    # In general Sieve of Sundaram, produces
    # primes smaller than (2*x + 2) for a number
    # given number x. Since we want primes smaller
    # than n, we reduce n to half
    nNew = (n - 2) // 2
 
    # This array is used to separate numbers
    # of the form i+j+2ij from others where
    # 1 <= i <= j
    marked = [ False for i in range(nNew + 1)]
 
    SieveOfSundaram(marked, nNew)
 
    count, prime_num = 0, 0
 
    # Find primes. Primes are of the form
    # 2*i + 1 such that marked[i] is false.
    for i in range(1, nNew + 1):
        if (marked[i] == False):
 
            prime_num = 2 * i + 1
 
            # For a given prime number p
            # number of distinct pairs(i,j)
            # where (i+j) = p are p/2
            count = count + (prime_num // 2)
 
    return count
 
# Driver Code
n = 12
print("Number of prime pairs: ",
             countPrimePairs(n))
 
# This code is contributed by Mohit kumar 29

// C# implementation of prime pairs
// whose sum is less than n
using System;
 
class GFG
{
     
// Sieve of Sundaram for generating
// prime numbers less than n
static void SieveOfSundaram(bool[] marked,
                            int nNew)
{
     
    // Main logic of Sundaram. Mark all numbers
    // of the form i + j + 2ij as true where
    // 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;
}
 
// Returns number of pairs with given conditions.
static int countPrimePairs(int n)
{
    // In general Sieve of Sundaram, produces
    // primes smaller than (2*x + 2) for a 
    // number given number x. Since we want
    // primes smaller than n, we reduce n to half
    int nNew = (n - 2) / 2;
 
    // This array is used to separate numbers
    // of the form i+j+2ij from others where
    // 1 <= i <= j
    // Initialize all elements as not marked
    bool[] marked = new bool[nNew + 1];
 
    SieveOfSundaram(marked, nNew);
    int count = 0, prime_num;
 
    // Find primes. Primes are of the form
    // 2*i + 1 such that marked[i] is false.
    for (int i = 1; i <= nNew; i++)
    {
        if (marked[i] == false)
        {
            prime_num = 2 * i + 1;
 
            // For a given prime number p
            // number of distinct pairs(i, j)
            // where (i + j) = p are p/2
            count = count + (prime_num / 2);
        }
    }
    return count;
}
 
// Driver code
public static void Main ()
{
    int n = 12;
    Console.WriteLine("Number of prime pairs: " +
                             countPrimePairs(n));
}
}
 
// This Code is Contribute by Mukul Singh.

<?php
// PHP implementation of prime pairs
// whose sum is less than n
 
// Sieve of Sundaram for generating
// prime numbers less than n
function SieveOfSundaram(&$marked, $nNew)
{
    // Main logic of Sundaram. Mark all
    // numbers of the form i + j + 2ij
    // as true where 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;
}
 
// Returns number of pairs with
// given conditions.
function countPrimePairs($n)
{
    // In general Sieve of Sundaram, produces
    // primes smaller than (2*x + 2) for a
    // number given number x. Since we want
    // primes smaller than n, we reduce n to half
    $nNew = ($n - 2) / 2;
 
    // This array is used to separate numbers
    // of the form i+j+2ij from others where
    // 1 <= i <= j
    $marked = array_fill(0, $nNew + 1, false);
 
    SieveOfSundaram($marked, $nNew);
 
    $count = 0;
 
    // Find primes. Primes are of the form
    // 2*i + 1 such that marked[i] is false.
    for ($i = 1; $i <= $nNew; $i++)
    {
        if ($marked[$i] == false)
        {
            $prime_num = 2 * $i + 1;
 
            // For a given prime number p
            // number of distinct pairs(i,j)
            // where (i+j) = p are p/2
            $count = $count + (int)($prime_num / 2);
        }
    }
 
    return $count;
}
 
// Driver Code
$n = 12;
echo "Number of prime pairs: " .
            countPrimePairs($n);
 
// This code is contributed by
// chandan_jnu
?>

<script>
 
// Javascript implementation of prime pairs
// whose sum is less than n   
 
// Sieve of Sundaram for generating
// prime numbers less than n
function SieveOfSundaram(marked, nNew)
{
     
    // Main logic of Sundaram. Mark all numbers
    // of the form i + j + 2ij as true where
    // 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;
}
 
// Returns number of pairs with given conditions.
function countPrimePairs(n)
{
     
    // In general Sieve of Sundaram, produces
    // primes smaller than (2*x + 2) for a number
    // given number x. Since we want primes smaller
    // than n, we reduce n to half
    var nNew = parseInt((n - 2) / 2);
 
    // This array is used to separate numbers of
    // the form i+j+2ij from others where
    // 1 <= i <= j
    // Initialize all elements as not marked
    marked = Array.from({length: nNew + 1}, (_, i) => false);
 
    SieveOfSundaram(marked, nNew);
    var count = 0, prime_num;
 
    // Find primes. Primes are of the form
    // 2*i + 1 such that marked[i] is false.
    for(i = 1; i <= nNew; i++)
    {
        if (marked[i] == false)
        {
            prime_num = 2 * i + 1;
 
            // For a given prime number p
            // number of distinct pairs(i, j)
            // where (i + j) = p are p/2
            count = count + parseInt(prime_num / 2);
        }
    }
    return count;
}
 
// Driver code
var n = 12;
document.write("Number of prime pairs: " +
               countPrimePairs(n));
 
// This code is contributed by Princi Singh
 
</script>

Producción: 

Number of prime pairs: 11

Este artículo es una contribución de Ayush Jauhari . 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.