Express a given number as a summation of 4 positive primes. If it is not possible to express then print “-1”.
Examples:
Input: 24 Output: 3 11 3 7 Explanation : 3+11+3+7 = 24 and 3, 11, 7 are all prime. Input: 46 Output: 11 11 17 7 explanation : 11+11+17+7 = 46 and 11, 7, 17 are all prime.
Approach : Every even integer greater than 2 can be expressed as the sum of two numbers by Goldbach’s conjecture.
Below are some facts for expressing a number as sum of 4 primes.
- Number must be greater than or equal to 8 as 2 is the smallest prime
- If given number is even, we can break it as (2 + 2) + x so that x remains even and can broken into two primes.
- If given number is odd, we can break it as (2 + 3) + x so that x remains even and can broken into two primes.
Now we can easily express n as sum of two primes using link
C++
// CPP program to express n as sum of 4 primes. #include <bits/stdc++.h> using namespace std; // function to check if a number is prime or not int isPrime(int x) { // does square root of the number int s = sqrt(x); // traverse from 2 to sqrt(n) for (int i = 2; i <= s; i++) // if any divisor found then non prime if (x % i == 0) return 0; // if no divisor is found then it is a prime return 1; } void Num(int x, int& a, int& b) { // iterates to check prime or not for (int i = 2; i <= x / 2; i++) { // calls function to check if i and x-i // is prime or not if (isPrime(i) && isPrime(x - i)) { a = i; b = x - i; // if two prime numbers are found, // then return return; } } } // function to generate 4 prime numbers adding upto n void generate(int n) { // if n<=7 then 4 numbers cannot sum to // get that number if (n <= 7) cout << "Impossible to form" << endl; // a and b stores the last two numbers int a, b; // if it is not even then 2 and 3 are first // two of sequence if (n % 2 != 0) { // calls the function to get the other // two prime numbers considering first two // primes as 2 and 3 (Note 2 + 3 = 5) Num(n - 5, a, b); // print 2 and 3 as the firsts two prime // and a and b as the last two. cout << "2 3 " << a << " " << b << endl; } // if it is even then 2 and 2 are first two // of sequence else { /// calls the function to get the other // two prime numbers considering first two // primes as 2 and 2 (Note 2 + 2 = 4) Num(n - 4, a, b); // print 2 and 2 as the firsts two prime // and a and b as the last two. cout << "2 2 " << a << " " << b << endl; } } // driver program to test the above function int main() { int n = 28; generate(n); return 0; } |
Java
// Java program to express n as sum of // 4 primes. class GFG { static int a = 0, b = 0; // function to check if a number // is prime or not static int isPrime(int x) { // does square root of the // number int s = (int)Math.sqrt(x); // traverse from 2 to sqrt(n) for (int i = 2; i <= s; i++) // if any divisor found // then non prime if (x % i == 0) return 0; // if no divisor is found // then it is a prime return 1; } static void Num(int x) { // iterates to check prime // or not for (int i = 2; i <= x / 2; i++) { // calls function to check // if i and x-i is prime // or not if (isPrime(i) != 0 && isPrime(x - i) != 0) { a = i; b = x - i; // if two prime numbers // are found, then return return; } } } // function to generate 4 prime // numbers adding upto n static void generate(int n) { // if n<=7 then 4 numbers cannot // sum to get that number if (n <= 7) System.out.println("Impossible" + " to form"); // if it is not even then 2 and 3 // are first two of sequence if (n % 2 != 0) { // calls the function to get the // other two prime numbers // considering first two primes // as 2 and 3 (Note 2 + 3 = 5) Num(n - 5); // print 2 and 3 as the firsts // two prime and a and b as the // last two. System.out.println("2 3 " + a + " " + b); } // if it is even then 2 and 2 are // first two of sequence else { /// calls the function to get the // other two prime numbers // considering first two primes as // 2 and 2 (Note 2 + 2 = 4) Num(n - 4); // print 2 and 2 as the firsts // two prime and a and b as the // last two. System.out.println("2 2 " + a + " " + b); } } // Driver function to test the above // function public static void main(String[] args) { int n = 28; generate(n); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to express # n as sum of 4 primes. import math; # function to check if a # number is prime or not def isPrime(x): # does square root # of the number s = int(math.sqrt(x)) # traverse from 2 to sqrt(n) for i in range(2,s+1): # if any divisor found # then non prime if (x % i == 0): return 0 # if no divisor is found # then it is a prime return 1 def Num(x): # iterates to check # prime or not ab=[0]*2 for i in range(2,int(x / 2)+1): # calls function to check # if i and x-i is prime # or not if (isPrime(i) != 0 and isPrime(x - i) != 0): ab[0] = i ab[1] = x - i # if two prime numbers # are found, then return return ab # function to generate 4 prime # numbers adding upto n def generate(n): # if n<=7 then 4 numbers cannot # sum to get that number if(n <= 7): print("Impossible to form") # if it is not even then 2 and # 3 are first two of sequence if (n % 2 != 0): # calls the function to get # the other two prime numbers # considering first two primes # as 2 and 3 (Note 2 + 3 = 5) ab=Num(n - 5) # print 2 and 3 as the firsts # two prime and a and b as the # last two. print("2 3",ab[0],ab[1]) # if it is even then 2 and 2 are # first two of sequence else: # calls the function to get # the other two prime numbers # considering first two primes # as 2 and 2 (Note 2 + 2 = 4) ab=Num(n - 4) # print 2 and 2 as the firsts # two prime and a and b as the # last two. print("2 2",ab[0],ab[1]) # Driver Code if __name__=='__main__': n = 28 generate(n) # This code is contributed by mits. |
C#
// C# program to express n as sum of // 4 primes. using System; class GFG { static int a = 0, b = 0; // function to check if a number // is prime or not static int isPrime(int x) { // does square root of the // number int s = (int)Math.Sqrt(x); // traverse from 2 to sqrt(n) for (int i = 2; i <= s; i++) // if any divisor found // then non prime if (x % i == 0) return 0; // if no divisor is found // then it is a prime return 1; } static void Num(int x) { // iterates to check prime // or not for (int i = 2; i <= x / 2; i++) { // calls function to check // if i and x-i is prime // or not if (isPrime(i) != 0 && isPrime(x - i) != 0) { a = i; b = x - i; // if two prime numbers // are found, then return return; } } } // function to generate 4 prime // numbers adding upto n static void generate(int n) { // if n<=7 then 4 numbers cannot // sum to get that number if (n <= 7) Console.Write("Impossible" + " to form"); // if it is not even then 2 and // 3 are first two of sequence if (n % 2 != 0) { // calls the function to get // the other two prime numbers // considering first two primes // as 2 and 3 (Note 2 + 3 = 5) Num(n - 5); // print 2 and 3 as the firsts // two prime and a and b as the // last two. Console.Write("2 3 " + a + " " + b); } // if it is even then 2 and 2 are // first two of sequence else { /// calls the function to get // the other two prime numbers // considering first two primes // as 2 and 2 (Note 2 + 2 = 4) Num(n - 4); // print 2 and 2 as the firsts // two prime and a and b as the // last two. Console.Write("2 2 " + a + " " + b); } } // Driver function to test the above // function public static void Main() { int n = 28; generate(n); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program to express // n as sum of 4 primes. $a = 0; $b = 0; // function to check if a // number is prime or not function isPrime($x) { // does square root // of the number $s = (int)(sqrt($x)); // traverse from 2 to sqrt(n) for ($i = 2; $i <= $s; $i++) // if any divisor found // then non prime if ($x % $i == 0) return 0; // if no divisor is found // then it is a prime return 1; } function Num($x) { global $a; global $b; // iterates to check // prime or not for ($i = 2; $i <= (int)($x / 2); $i++) { // calls function to check // if i and x-i is prime // or not if (isPrime($i) != 0 && isPrime($x - $i) != 0) { $a = $i; $b = $x - $i; // if two prime numbers // are found, then return return; } } } // function to generate 4 prime // numbers adding upto n function generate($n) { global $a; global $b; // if n<=7 then 4 numbers cannot // sum to get that number if ($n <= 7) echo "Impossible to form"; // if it is not even then 2 and // 3 are first two of sequence if ($n % 2 != 0) { // calls the function to get // the other two prime numbers // considering first two primes // as 2 and 3 (Note 2 + 3 = 5) Num($n - 5); // print 2 and 3 as the firsts // two prime and a and b as the // last two. echo "2 3 $a $b"; } // if it is even then 2 and 2 are // first two of sequence else { // calls the function to get // the other two prime numbers // considering first two primes // as 2 and 2 (Note 2 + 2 = 4) Num($n - 4); // print 2 and 2 as the firsts // two prime and a and b as the // last two. echo "2 2 $a $b"; } } // Driver Code $n = 28; generate($n); // This code is contributed by mits. ?> |
Javascript
<script> // JavaScript program to express n as sum of // 4 primes. let a = 0, b = 0; // function to check if a number // is prime or not function isPrime(x) { // does square root of the // number let s = Math.sqrt(x); // traverse from 2 to sqrt(n) for (let i = 2; i <= s; i++) // if any divisor found // then non prime if (x % i == 0) return 0; // if no divisor is found // then it is a prime return 1; } function Num(x) { // iterates to check prime // or not for (let i = 2; i <= x / 2; i++) { // calls function to check // if i and x-i is prime // or not if (isPrime(i) != 0 && isPrime(x - i) != 0) { a = i; b = x - i; // if two prime numbers // are found, then return return; } } } // function to generate 4 prime // numbers adding upto n function generate(n) { // if n<=7 then 4 numbers cannot // sum to get that number if (n <= 7) document.write("Impossible" + " to form"); // if it is not even then 2 and 3 // are first two of sequence if (n % 2 != 0) { // calls the function to get the // other two prime numbers // considering first two primes // as 2 and 3 (Note 2 + 3 = 5) Num(n - 5); // print 2 and 3 as the firsts // two prime and a and b as the // last two. document.write("2 3 " + a + " " + b); } // if it is even then 2 and 2 are // first two of sequence else { /// calls the function to get the // other two prime numbers // considering first two primes as // 2 and 2 (Note 2 + 2 = 4) Num(n - 4); // print 2 and 2 as the firsts // two prime and a and b as the // last two. document.write("2 2 " + a + " " + b); } } // Driver Code let n = 28; generate(n); </script> |
Output:
2 2 5 19
Time complexity: O(n sqrt(n))
Auxiliary space: O(1)
This article is contributed by Raja Vikramaditya If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
