Dado un número par (mayor que 2), imprima dos números primos cuya suma sea igual al número dado. Puede haber varias combinaciones posibles. Imprima solo el primer par.
Un punto interesante es que siempre existe una solución según la conjetura de Goldbach .
Ejemplos:
Input: n = 74 Output: 3 71 Input : n = 1024 Output: 3 1021 Input: n = 66 Output: 5 61 Input: n = 9990 Output: 17 9973
La idea es encontrar todos los primos menores o iguales al número dado N usando la Criba de Eratóstenes. Una vez que tenemos una array que dice todos los números primos, podemos atravesar esta array para encontrar un par con la suma dada.
C++
// C++ program to find a prime number pair whose sum is
// equal to given number
// C++ program to print super primes less than or equal to n.
#include <bits/stdc++.h>
using namespace std;
// Generate all prime numbers less than n.
bool SieveOfEratosthenes(int n, bool isPrime[])
{
// Initialize all entries of boolean array as true. A
// value in isPrime[i] will finally be false if i is Not
// a prime, else true bool isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int p = 2; p * p <= n; p++) {
// If isPrime[p] is not changed, then it is a prime
if (isPrime[p] == true) {
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Prints a prime pair with given sum
void findPrimePair(int n)
{
// Generating primes using Sieve
bool isPrime[n + 1];
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to find first pair
for (int i = 0; i < n; i++) {
if (isPrime[i] && isPrime[n - i]) {
cout << i << " " << (n - i);
return;
}
}
}
// Driven program
int main()
{
int n = 74;
findPrimePair(n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to find a prime number pair whose sum is
// equal to given number
// C program to print super primes less than or equal to n.
#include <stdio.h>
#include <stdbool.h>
// Generate all prime numbers less than n.
bool SieveOfEratosthenes(int n, bool isPrime[])
{
// Initialize all entries of boolean array as true. A
// value in isPrime[i] will finally be false if i is Not
// a prime, else true bool isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int p = 2; p * p <= n; p++) {
// If isPrime[p] is not changed, then it is a prime
if (isPrime[p] == true) {
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
}
// Prints a prime pair with given sum
void findPrimePair(int n)
{
// Generating primes using Sieve
bool isPrime[n + 1];
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to find first
// pair
for (int i = 0; i < n; i++) {
if (isPrime[i] && isPrime[n - i]) {
printf("%d %d",i,n-i);
return;
}
}
}
// Driven program
int main()
{
int n = 74;
findPrimePair(n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to find a prime number pair whose sum is
// equal to given number
// Java program to print super primes less than or equal to n.
class GFG {
// Generate all prime numbers less than n.
static boolean SieveOfEratosthenes(int n, boolean isPrime[])
{
// Initialize all entries of boolean array as true.
// A value in isPrime[i] will finally be false if i
// is Not a prime, else true bool isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int p = 2; p * p <= n; p++) {
// If isPrime[p] is not changed, then it is a
// prime
if (isPrime[p] == true) {
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
return false;
}
// Prints a prime pair with given sum
static void findPrimePair(int n)
{
// Generating primes using Sieve
boolean isPrime[] = new boolean[n + 1];
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to find first pair
for (int i = 0; i < n; i++) {
if (isPrime[i] && isPrime[n - i]) {
System.out.print(i + " " + (n - i));
return;
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 74;
findPrimePair(n);
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python 3
# Python 3 program to find a prime number # pair whose sum is equal to given number # Python 3 program to print super primes # less than or equal to n. # Generate all prime numbers less than n. def SieveOfEratosthenes(n, isPrime): # Initialize all entries of boolean # array as True. A value in isPrime[i] # will finally be False if i is Not a # prime, else True bool isPrime[n+1] isPrime[0] = isPrime[1] = False for i in range(2, n+1): isPrime[i] = True p = 2 while(p*p <= n): # If isPrime[p] is not changed, # then it is a prime if (isPrime[p] == True): # Update all multiples of p i = p*p while(i <= n): isPrime[i] = False i += p p += 1 # Prints a prime pair with given sum def findPrimePair(n): # Generating primes using Sieve isPrime = [0] * (n+1) SieveOfEratosthenes(n, isPrime) # Traversing all numbers to find # first pair for i in range(0, n): if (isPrime[i] and isPrime[n - i]): print(i,(n - i)) return # Driven program n = 74 findPrimePair(n) # This code is contributed by # Smitha Dinesh Semwal
C#
// C# program to find a prime number pair whose
// sum is equal to given number
// C# program to print super primes less than
// or equal to n.
using System;
class GFG
{
// Generate all prime numbers less than n.
static bool SieveOfEratosthenes(int n, bool []isPrime)
{
// Initialize all entries of boolean
// array as true. A value in isPrime[i]
// will finally be false if i is Not a
// prime, else true bool isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int p = 2; p * p <= n; p++)
{
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true)
{
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
return false;
}
// Prints a prime pair with given sum
static void findPrimePair(int n)
{
// Generating primes using Sieve
bool []isPrime=new bool[n + 1];
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to find first
// pair
for (int i = 0; i < n; i++)
{
if (isPrime[i] && isPrime[n - i])
{
Console.Write(i + " " + (n - i));
return;
}
}
}
// Driver code
public static void Main ()
{
int n = 74;
findPrimePair(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find a prime
// number pair whose sum is equal
// to given number
// Generate all prime numbers
// less than n.
function SieveOfEratosthenes($n, &$isPrime)
{
// Initialize all entries of
// boolean array as true. A value
// in isPrime[i] will finally
// be false if i is Not a prime,
// else true bool isPrime[n+1];
$isPrime[0] = $isPrime[1] = false;
for ($i = 2; $i <= $n; $i++)
$isPrime[$i] = true;
for ($p = 2; $p * $p <= $n; $p++)
{
// If isPrime[p] is not changed,
// then it is a prime
if ($isPrime[$p] == true)
{
// Update all multiples of p
for ($i = $p * $p;
$i <= $n; $i += $p)
$isPrime[$i] = false;
}
}
}
// Prints a prime pair with given sum
function findPrimePair($n)
{
// Generating primes using Sieve
$isPrime = array_fill(0, $n + 1, NULL);
SieveOfEratosthenes($n, $isPrime);
// Traversing all numbers
// to find first pair
for ($i = 0; $i < $n; $i++)
{
if ($isPrime[$i] &&
$isPrime[$n - $i])
{
echo $i . " " . ($n - $i);
return;
}
}
}
// Driver Code
$n = 74;
findPrimePair($n);
// This code is contributed
// by ChitraNayal
?>
Javascript
<script>
// Javascript program to find a prime number pair whose
// sum is equal to given number
// Java program to print super primes less than
// or equal to n.
// Generate all prime numbers less than n.
function SieveOfEratosthenes(n,isPrime)
{
// Initialize all entries of boolean
// array as true. A value in isPrime[i]
// will finally be false if i is Not a
// prime, else true bool isPrime[n+1];
isPrime[0] = isPrime[1] = false;
for (let i = 2; i <= n; i++)
isPrime[i] = true;
for (let p = 2; p * p <= n; p++)
{
// If isPrime[p] is not changed,
// then it is a prime
if (isPrime[p] == true)
{
// Update all multiples of p
for (let i = p * p; i <= n; i += p)
isPrime[i] = false;
}
}
return false;
}
// Prints a prime pair with given sum
function findPrimePair(n)
{
// Generating primes using Sieve
let isPrime = new Array(n+1);
for(let i=0;i<n+1;i++)
{
isPrime[i]=false;
}
SieveOfEratosthenes(n, isPrime);
// Traversing all numbers to find first
// pair
for (let i = 0; i < n; i++)
{
if (isPrime[i] && isPrime[n - i])
{
document.write(i + " " + (n - i));
return;
}
}
}
// Driver code
let n = 74;
findPrimePair(n);
// This code is contributed by rag2127
</script>
Producción:
3 71
Complejidad del tiempo : O(n*log(logn))
Espacio Auxiliar: O(n)
Este artículo es una contribución de Rakesh Kumar . 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