Dado un número impar, necesitamos expresarlo como la suma de tres números primos como máximo.
Ejemplos:
Input : 27 Output : 27 = 3 + 5 + 19 Input : 15 Output : 15 = 2 + 13
Enfoque: Aquí, usamos la conjetura de Goldbach para resolver este problema. Dice que cualquier número entero par puede expresarse como la suma de dos números primos.
Aquí tenemos tres casos:
1) Cuando N es un número primo, imprime el número.
2) Cuando (N-2) es un número primo, escribe 2 y N-2.
3) Exprese N como 3 + (N-3). Obviamente, N-3 será un número par (la resta de un impar de otro impar da como resultado un par). Entonces, según la conjetura de Goldbach, se puede expresar como la suma de dos números primos. Entonces, imprime 3 y otros dos números primos.
C++
// CPP program to express N as sum of at-most
// three prime numbers.
#include <bits/stdc++.h>
using namespace std;
// Function to check if a number is prime or not.
bool isPrime(int x)
{
if (x == 0 || x == 1)
return false;
for (int i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}
// Prints at most three prime numbers whose
// sum is n.
void findPrimes(int n)
{
if (isPrime(n)) // CASE-I
cout << n << endl;
else if (isPrime(n - 2)) // CASE-II
cout << 2 << " " << n - 2 << endl;
else // CASE-III
{
cout << 3 << " ";
n = n - 3;
for (int i = 0; i < n; i++) {
if (isPrime(i) && isPrime(n - i)) {
cout << i << " " << (n - i);
break;
}
}
}
}
// Driver code
int main()
{
int n = 27;
findPrimes(n);
return 0;
}
Java
// Java program to express N as sum
// of at-most three prime numbers.
import java.util.*;
class GFG{
// Function to check if a
// number is prime or not.
public static boolean isPrime(int x)
{
if (x == 0 || x == 1)
return false;
for (int i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}
// Prints at most three prime
// numbers whose sum is n.
public static void findPrimes(int n)
{
if (isPrime(n)) // CASE-I
System.out.print( n );
else if (isPrime(n - 2)) // CASE-II
System.out.print( 2 + " " +
(n - 2) );
else // CASE-III
{
System.out.print( 3 + " ");
n = n - 3;
for (int i = 0; i < n; i++) {
if (isPrime(i) && isPrime(n - i)) {
System.out.print( i + " " +
(n - i));
break;
}
}
}
}
// driver code
public static void main(String[] args)
{
int n = 27;
findPrimes(n);
}
}
// This code is contributed by rishabh_jain
Python3
# Python3 program to express N as
# sum of at-most three prime numbers
# Function to check if a number
# is prime or not.
def isPrime(x):
if(x == 0 or x == 1) :
return 0
i = 2
while i * i <= x :
if (x % i == 0) :
return 0
i = i + 1
return 1
# Prints at most three prime numbers
# whose sum is n.
def findPrimes(n) :
if (isPrime(n)):
# CASE-I
print(n, end = " ")
elif (isPrime(n - 2)) :
# CASE-II
print ("2", end = " ")
print (n - 2, end = " " )
else:
#CASE-III
print ( "3", end = " " )
n = n - 3
i = 0
while i < n :
if (isPrime(i) and isPrime(n - i)) :
print(i, end = " ")
print ((n - i), end = " ")
break
i = i + 1
# Driver Code
n = 27;
findPrimes(n);
# This code is contributed by rishabh_jain
C#
// C# program to express N as sum
// of at-most three prime numbers.
using System;
class GFG
{
// Function to check if a
// number is prime or not.
public static bool isPrime(int x)
{
if (x == 0 || x == 1)
return false;
for (int i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}
// Prints at most three prime
// numbers whose sum is n.
public static void findPrimes(int n)
{
if (isPrime(n)) // CASE-I
Console.WriteLine( n );
else if (isPrime(n - 2)) // CASE-II
Console.Write( 2 + " " +
(n - 2) );
else // CASE-III
{
Console.Write( 3 + " ");
n = n - 3;
for (int i = 0; i < n; i++) {
if (isPrime(i) && isPrime(n - i))
{
Console.WriteLine( i + " " +
(n - i));
break;
}
}
}
}
// Driver code
public static void Main()
{
int n = 27;
findPrimes(n);
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to express
// N as sum of at-most
// three prime numbers.
// Function to check if a
// number is prime or not.
function isPrime($x)
{
if ($x == 0 || $x == 1)
return false;
for ($i = 2; $i * $i <= $x; ++$i)
if ($x % $i == 0)
return false;
return true;
}
// Prints at most three prime
// numbers whose sum is n.
function findPrimes($n)
{
// CASE-I
if (isPrime($n))
echo($n);
// CASE-II
else if (isPrime($n - 2))
echo(2 . " " . ($n - 2));
// CASE-III
else
{
echo(3 . " ");
$n = $n - 3;
for ($i = 0; $i < $n; $i++)
{
if (isPrime($i) &&
isPrime($n - $i))
{
echo($i . " " .
($n - $i));
break;
}
}
}
}
// Driver code
$n = 27;
findPrimes($n);
// This code is contributed by Ajit.
?>
Javascript
<script>
// javascript program to express N as sum
// of at-most three prime numbers.
// Function to check if a
// number is prime or not.
function isPrime(x)
{
if (x == 0 || x == 1)
return false;
for (let i = 2; i * i <= x; ++i)
if (x % i == 0)
return false;
return true;
}
// Prints at most three prime
// numbers whose sum is n.
function findPrimes(n)
{
if (isPrime(n)) // CASE-I
document.write( n );
else if (isPrime(n - 2)) // CASE-II
document.write( 2 + " " +
(n - 2) );
else // CASE-III
{
document.write( 3 + " ");
n = n - 3;
for (let i = 0; i < n; i++) {
if (isPrime(i) && isPrime(n - i)) {
document.write( i + " " +
(n - i));
break;
}
}
}
}
// Driver code
let n = 27;
findPrimes(n);
// This code is contributed by susmitakundugoaldanga.
</script>
Producción :
3 5 19
Publicación traducida automáticamente
Artículo escrito por Harsha_Mogali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA