Check if a number can be written as a sum of ‘k’ prime numbers
Given two numbers N and K. We need to find out if ‘N’ can be written as sum of ‘K’ prime numbers.
Given N <= 10^9
Examples :
Input : N = 10 K = 2 Output : Yes 10 can be written as 5 + 5 Input : N = 2 K = 2 Output : No
The idea is to use Goldbach’s conjecture which says that every even integer (greater than 2) can be expressed as sum of two primes.
If the N >= 2K and K = 1: the answer will be Yes if N is a prime number
If N >= 2K and K = 2: If N is an even number answer will be Yes(Goldbach’s conjecture) and if N is odd answer will be No if N-2 is not a prime number and Yes if N-2 is a prime number. This is because we know odd + odd = even and even + odd = odd. So when N is odd, and K = 2 one number must be 2 as it is the only even prime number so now the answer depends on whether N-2 is odd or not.
If N >= 2K and K >= 3: Answer will always be Yes. When N is even N – 2*(K-2) is also even so N – 2*(K – 2) can be written as sum of two prime numbers (Goldbach’s conjecture) p, q and N can be written as 2, 2 …..K – 2 times, p, q. When N is odd N – 3 -2*(K – 3) is even so it can be written as sum of two prime numbers p, q and N can be written as 2, 2 …..K-3 times, 3, p, 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> |
Output :
Yes
Time Complexity: O(sqrt(x))
Auxiliary Space: O(1)
This article is contributed by Ayush Jha