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