N expresado como suma de 4 números primos

Expresar un número dado como suma de 4 números primos positivos. Si no es posible expresar entonces escriba “-1”.

Ejemplos: 

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.

Enfoque: todo número par mayor que 2 se puede expresar como la suma de dos números mediante la conjetura de Goldbach .
A continuación se presentan algunos hechos para expresar un número como suma de 4 números primos.  

  • El número debe ser mayor o igual a 8 ya que 2 es el primo más pequeño
  • Si el número dado es par, podemos dividirlo como (2 + 2) + x para que x siga siendo par y pueda dividirse en dos números primos.
  • Si el número dado es impar, podemos dividirlo como (2 + 3) + x para que x siga siendo par y pueda dividirse en dos números primos.

Ahora podemos expresar fácilmente n como suma de dos números primos usando el vínculo 

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>

Producción: 

2 2 5 19

Complejidad temporal: O(n sqrt(n)) 
Espacio auxiliar: O(1)

Este artículo es una contribución de Raja Vikramaditya . 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 *