Comprueba si un número se puede escribir como una suma de ‘k’ números primos

Dados dos números N y K. Necesitamos averiguar si ‘N’ se puede escribir como suma de ‘K’ números primos. 
Dado N <= 10^9

Ejemplos: 

Input  : N = 10 K = 2
Output : Yes 
        10 can be written as 5 + 5

Input  : N = 2 K = 2
Output : No

La idea es usar la conjetura de Goldbach que dice que todo número par (mayor que 2) se puede expresar como la suma de dos números primos.
Si N >= 2K y K = 1: la respuesta será Sí si y sólo si N es un número primo
Si N >= 2K y K = 2: Si N es un número par la respuesta será Sí (conjetura de Goldbach) y si N es La respuesta impar será No si N-2 no es un número primo y Sí si N-2 es un número primo. Esto se debe a que sabemos impar + impar = par y par + impar = impar. Entonces, cuando N es impar y K = 2, un número debe ser 2, ya que es el único número primo par, por lo que ahora la respuesta depende de si N-2 es impar o no. 
Si N >= 2K y K >= 3:La respuesta siempre será Sí. Cuando N es par N – 2*(K-2) también es par, entonces N – 2*(K – 2) se puede escribir como la suma de dos números primos (conjetura de Goldbach) p, q y N se pueden escribir como 2, 2 …..K – 2 veces, p, q. Cuando N es impar N – 3 -2*(K – 3) es par, por lo que puede escribirse como la suma de dos números primos p, q y N puede escribirse como 2, 2 …..K-3 veces, 3, pag q 

C++

// C++ implementation to check if N can be
// written as sum of k primes
#include<bits/stdc++.h>
using namespace std;
 
// Checking if a number is prime or not
bool isprime(int x)
{
   
    // check for numbers from 2 to sqrt(x)
    // if it is divisible return false
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}
 
// Returns true if N can be written as sum
// of K primes
bool isSumOfKprimes(int N, int K)
{
    // N < 2K directly return false
    if (N < 2*K)
        return false;
 
    // If K = 1 return value depends on primality of N
    if (K == 1)
        return isprime(N);
 
    if (K == 2)
    {
        // if N is even directly return true;
        if (N % 2 == 0)
            return true;
 
        // If N is odd, then one prime must
        // be 2. All other primes are odd
        // and cannot have a pair sum as even.
        return isprime(N - 2);
    }
 
    // If K >= 3 return true;
    return true;
}
 
// Driver function
int main()
{
    int n = 10, k = 2;
    if (isSumOfKprimes (n, k))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Java

// Java implementation to check if N can be
// written as sum of k primes
public class Prime
{
    // Checking if a number is prime or not
    static boolean isprime(int x)
    {
        // check for numbers from 2 to sqrt(x)
        // if it is divisible return false
        for (int i=2; i*i<=x; i++)
            if (x%i == 0)
             
                return false;
        return true;
    }
     
    // Returns true if N can be written as sum
    // of K primes
    static boolean isSumOfKprimes(int N, int K)
    {
        // N < 2K directly return false
        if (N < 2*K)
            return false;
         
        // If K = 1 return value depends on primality of N
        if (K == 1)
            return isprime(N);
             
        if (K == 2)
        {
            // if N is even directly return true;
            if (N%2 == 0)
                return true;
                 
            // If N is odd, then one prime must
            // be 2. All other primes are odd
            // and cannot have a pair sum as even.
            return isprime(N - 2);
        }
         
        // If K >= 3 return true;
        return true;
    }
     
    public static void main (String[] args)
    {
        int n = 10, k = 2;
        if (isSumOfKprimes (n, k))
            System.out.print("Yes");
        else
            System.out.print("No");
    }
}
// Contributed by Saket Kumar

Python3

# Python implementation to check
# if N can be written as sum of
# k primes
 
# Checking if a number is prime
# or not
 
 
def isprime(x):
 
    # check for numbers from 2
    # to sqrt(x) if it is divisible
    # return false
    i = 2
    while(i * i <= x):
        if (x % i == 0):
            return 0
        i += 1
    return 1
 
# Returns true if N can be written
# as sum of K primes
 
 
def isSumOfKprimes(N, K):
 
    # N < 2K directly return false
    if (N < 2 * K):
        return 0
 
    # If K = 1 return value depends
    # on primality of N
    if (K == 1):
        return isprime(N)
 
    if (K == 2):
 
        # if N is even directly
        # return true;
        if (N % 2 == 0):
            return 1
 
        # If N is odd, then one
        # prime must be 2. All
        # other primes are odd
        # and cannot have a pair
        # sum as even.
        return isprime(N - 2)
 
    # If K >= 3 return true;
    return 1
 
 
# Driver function
n = 15
k = 2
if (isSumOfKprimes(n, k)):
    print("Yes")
else:
    print("No")
 
# This code is Contributed by Sam007.

C#

// C# implementation to check if N can be
// written as sum of k primes
using System;
         
class GFG {
     
    // Checking if a number is prime or not
    static bool isprime(int x)
    {
        // check for numbers from 2 to sqrt(x)
        // if it is divisible return false
        for (int i = 2; i * i <= x; i++)
            if (x % i == 0)
             
                return false;
        return true;
    }
     
    // Returns true if N can be written as sum
    // of K primes
    static bool isSumOfKprimes(int N, int K)
    {
        // N < 2K directly return false
        if (N < 2 * K)
            return false;
         
        // If K = 1 return value depends on primality of N
        if (K == 1)
            return isprime(N);
             
        if (K == 2)
        {
            // if N is even directly return true;
            if (N % 2 == 0)
                return true;
                 
            // If N is odd, then one prime must
            // be 2. All other primes are odd
            // and cannot have a pair sum as even.
            return isprime(N - 2);
        }
         
        // If K >= 3 return true;
        return true;
    }
     
    // Driver function
    public static void Main ()
    {
        int n = 10, k = 2;
        if (isSumOfKprimes (n, k))
            Console.Write("Yes");
        else
            Console.Write("No");
    }
}
 
// This code is contributed by Sam007

PHP

<?php
// PHP implementation to check
// if N can be written as sum
// of k primes
 
// Checking if a number
// is prime or not
function isprime($x)
{
    // check for numbers from 2
    // to sqrt(x) if it is
    // divisible return false
    for ($i = 2; $i * $i <= $x; $i++)
        if ($x % $i == 0)
            return false;
    return true;
}
 
// Returns true if N can be
// written as sum of K primes
function isSumOfKprimes($N, $K)
{
    // N < 2K directly return false
    if ($N < 2 * $K)
        return false;
 
    // If K = 1 return value
    // depends on primality of N
    if ($K == 1)
        return isprime($N);
 
    if ($K == 2)
    {
        // if N is even directly
        // return true;
        if ($N % 2 == 0)
            return true;
 
        // If N is odd, then one prime
        // must be 2. All other primes
        // are odd and cannot have a
        // pair sum as even.
        return isprime($N - 2);
    }
 
    // If K >= 3 return true;
    return true;
}
 
// Driver Code
$n = 10; $k = 2;
if (isSumOfKprimes ($n, $k))
    echo "Yes";
else
    echo"No" ;
 
// This code is contributed by vt
?>

Javascript

<script>
// javascript implementation to check if N can be
// written as sum of k primes
 
    // Checking if a number is prime or not
    function isprime(x)
    {
     
        // check for numbers from 2 to sqrt(x)
        // if it is divisible return false
        for (i = 2; i * i <= x; i++)
            if (x % i == 0)
 
                return false;
        return true;
    }
 
    // Returns true if N can be written as sum
    // of K primes
    function isSumOfKprimes(N, K)
    {
     
        // N < 2K directly return false
        if (N < 2 * K)
            return false;
 
        // If K = 1 return value depends on primality of N
        if (K == 1)
            return isprime(N);
 
        if (K == 2)
        {
         
            // if N is even directly return true;
            if (N % 2 == 0)
                return true;
 
            // If N is odd, then one prime must
            // be 2. All other primes are odd
            // and cannot have a pair sum as even.
            return isprime(N - 2);
        }
 
        // If K >= 3 return true;
        return true;
    }
 
    // Driver code
        var n = 10, k = 2;
        if (isSumOfKprimes(n, k))
            document.write("Yes");
        else
            document.write("No");
 
// This code is contributed by gauravrajput1
</script>

Producción : 

Yes

Complejidad de tiempo: O(sqrt(x))
Espacio auxiliar: O(1)

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

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *