Comprueba si un número primo se puede expresar como la suma de dos números primos

Dado un número primo  . La tarea es verificar si es posible expresar  como suma de dos números primos separados.
Nota : El rango de N es menor que 10 ⁸ .

Ejemplos: 

Input : N = 13
Output : Yes
Explanation : The number 13 can be written as 11 + 2, 
here 11 and 2 are both prime.

Input : N = 11
Output : No

Solución simple : una solución simple es crear un tamiz para almacenar todos los números primos menores que el número N. Luego ejecute un ciclo de 1 a N y verifique si  y  son primos o no. En caso afirmativo, escriba Sí, de lo contrario, No.

Solución eficiente : excepto el 2, todos los números primos son impares. Por lo tanto, no es posible representar un número primo (que es impar) para que se escriba como una suma de dos números primos impares, por lo que estamos seguros de que uno de los dos números primos debe ser 2. Entonces, debemos verificar si n- 2 es primo o no. Si se mantiene, imprimimos Sí, de lo contrario, No.
Por ejemplo, si el número es 19, entonces tenemos que verificar si 19-2 = 17 es un número primo o no. Si 17 es un número primo, escriba sí, de lo contrario, escriba no.

A continuación se muestra la implementación del enfoque anterior: 

// C++ program to check if a prime number
// can be expressed as sum of
// two Prime Numbers
#include <bits/stdc++.h>
using namespace std;
 
// Function to check whether a number
// is prime or not
bool isPrime(int n)
{
    if (n <= 1)
        return false;
 
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return false;
    }
 
    return true;
}
 
// Function to check if a prime number
// can be expressed as sum of
// two Prime Numbers
bool isPossible(int N)
{
    // if the number is prime,
    // and number-2 is also prime
    if (isPrime(N) && isPrime(N - 2))
        return true;
    else
        return false;
}
 
// Driver code
int main()
{
    int n = 13;
 
    if (isPossible(n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java program to check if a prime number
// can be expressed as sum of
// two Prime Numbers
 
public class GFG{
     
    // Function to check whether a number
    // is prime or not
    static boolean isPrime(int n)
    {
        if (n <= 1)
            return false;
     
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0)
                return false;
        }
     
        return true;
    }
     
    // Function to check if a prime number
    // can be expressed as sum of
    // two Prime Numbers
    static boolean isPossible(int N)
    {
        // if the number is prime,
        // and number-2 is also prime
        if (isPrime(N) && isPrime(N - 2))
            return true;
        else
            return false;
    }
     
     // Driver code
     public static void main(String []args){
          
        int n = 13;
     
        if (isPossible(n) == true)
            System.out.println("Yes");
        else
            System.out.println("No");
     }
     // This code is contributed by ANKITRAI1
}

# Python3 program to check if a prime
# number can be expressed as sum of
# two Prime Numbers
import math
 
# Function to check whether a number
# is prime or not
def isPrime(n):
    if n <= 1:
        return False
     
    if n == 2:
        return True
         
    if n%2 == 0:
        return False
         
    for i in range(3, int(math.sqrt(n))+1, 2):
        if n%i == 0:
            return False
    return True
 
# Function to check if a prime number
# can be expressed as sum of
# two Prime Numbers
def isPossible(n):
 
    # if the number is prime,
    # and number-2 is also prime
    if isPrime(n) and isPrime(n - 2):
        return True
    else:
        return False
 
# Driver code
n = 13
if isPossible(n) == True:
    print("Yes")
else:
    print("No")
     
# This code is contributed by Shrikant13

// C# program to check if a prime
// number can be expressed as sum
// of two Prime Numbers
using System;
 
class GFG
{
 
// Function to check whether a
// number is prime or not
static bool isPrime(int n)
{
    if (n <= 1)
        return false;
 
    for (int i = 2;
             i <= Math.Sqrt(n); i++)
    {
        if (n % i == 0)
            return false;
    }
 
    return true;
}
 
// Function to check if a prime
// number can be expressed as sum
// of two Prime Numbers
static bool isPossible(int N)
{
    // if the number is prime,
    // and number-2 is also prime
    if (isPrime(N) && isPrime(N - 2))
        return true;
    else
        return false;
}
 
// Driver code
public static void Main()
{
    int n = 13;
 
    if (isPossible(n) == true)
        Console.Write("Yes");
    else
        Console.Write("No");
}
}
 
// This code is contributed
// by ChitraNayal

<?php
// PHP program to check if a prime
// number can be expressed as sum
// of two Prime Numbers
 
// Function to check whether a
// number is prime or not
function isPrime($n)
{
    if ($n <= 1)
        return false;
 
    for ($i = 2; $i <= sqrt($n); $i++)
    {
        if ($n % $i == 0)
            return false;
    }
 
    return true;
}
 
// Function to check if a prime
// number can be expressed as sum
// of two Prime Numbers
function isPossible($N)
{
    // if the number is prime,
    // and number-2 is also prime
    if (isPrime($N) && isPrime($N - 2))
        return true;
    else
        return false;
}
 
// Driver code
$n = 13;
 
if (isPossible($n))
    echo ("Yes");
else
    echo("No");
 
// This code is contributed
// by Shivi_Aggarwal
?>

<script>
 
// Javascript program to check if a
// prime number can be expressed as
// sum of two Prime Numbers
 
// Function to check whether a number
// is prime or not
function isPrime(n)
{
    if (n <= 1)
        return false;
 
    for(var i = 2; i <= parseInt(Math.sqrt(n)); i++)
    {
        if (n % i == 0)
            return false;
    }
 
    return true;
}
 
// Function to check if a prime number
// can be expressed as sum of
// two Prime Numbers
function isPossible(N)
{
     
    // If the number is prime,
    // and number-2 is also prime
    if (isPrime(N) && isPrime(N - 2))
        return true;
    else
        return false;
}
 
// Driver code
var n = 13;
if (isPossible(n))
    document.write("Yes");
else
    document.write("No");
     
// This code is contributed by noob2000
 
</script>

Yes

Complejidad de tiempo: O(sqrt(n))

Espacio Auxiliar: O(1)