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