La conjetura de Goldbach es uno de los problemas sin resolver más antiguos y conocidos de la teoría de números de las matemáticas. Todo entero par mayor que 2 se puede expresar como la suma de dos números primos.
Ejemplos:
Input : n = 44 Output : 3 + 41 (both are primes) Input : n = 56 Output : 3 + 53 (both are primes)
- Encuentra los números primos usando Sieve of Sundaram
- Compruebe si el número introducido es un número par mayor que 2 o no, si no hay retorno.
- En caso afirmativo, reste uno por uno un número primo de N y luego verifique si la diferencia también es un número primo. En caso afirmativo, expréselo como una suma.
C++
// C++ program to implement Goldbach's conjecture #include<bits/stdc++.h> using namespace std; const int MAX = 10000; // Array to store all prime less than and equal to 10^6 vector <int> primes; // Utility function for Sieve of Sundaram void sieveSundaram() { // In general Sieve of Sundaram, produces primes smaller // than (2*x + 2) for a number given number x. Since // we want primes smaller than MAX, we reduce MAX to half // This array is used to separate numbers of the form // i + j + 2*i*j from others where 1 <= i <= j bool marked[MAX/2 + 100] = {0}; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for (int i=1; i<=(sqrt(MAX)-1)/2; i++) for (int j=(i*(i+1))<<1; j<=MAX/2; j=j+2*i+1) marked[j] = true; // Since 2 is a prime number primes.push_back(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for (int i=1; i<=MAX/2; i++) if (marked[i] == false) primes.push_back(2*i + 1); } // Function to perform Goldbach's conjecture void findPrimes(int n) { // Return if number is not even or less than 3 if (n<=2 || n%2 != 0) { cout << "Invalid Input \n"; return; } // Check only upto half of number for (int i=0 ; primes[i] <= n/2; i++) { // find difference by subtracting current prime from n int diff = n - primes[i]; // Search if the difference is also a prime number if (binary_search(primes.begin(), primes.end(), diff)) { // Express as a sum of primes cout << primes[i] << " + " << diff << " = " << n << endl; return; } } } // Driver code int main() { // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); return 0; }
Java
// Java program to implement Goldbach's conjecture import java.util.*; class GFG { static int MAX = 10000; // Array to store all prime less // than and equal to 10^6 static ArrayList<Integer> primes = new ArrayList<Integer>(); // Utility function for Sieve of Sundaram static void sieveSundaram() { // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for // a number given number x. Since // we want primes smaller than MAX, // we reduce MAX to half This array is // used to separate numbers of the form // i + j + 2*i*j from others where 1 <= i <= j boolean[] marked = new boolean[MAX / 2 + 100]; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for (int i = 1; i <= (Math.sqrt(MAX) - 1) / 2; i++) for (int j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1) marked[j] = true; // Since 2 is a prime number primes.add(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for (int i = 1; i <= MAX / 2; i++) if (marked[i] == false) primes.add(2 * i + 1); } // Function to perform Goldbach's conjecture static void findPrimes(int n) { // Return if number is not even or less than 3 if (n <= 2 || n % 2 != 0) { System.out.println("Invalid Input "); return; } // Check only upto half of number for (int i = 0 ; primes.get(i) <= n / 2; i++) { // find difference by subtracting // current prime from n int diff = n - primes.get(i); // Search if the difference is // also a prime number if (primes.contains(diff)) { // Express as a sum of primes System.out.println(primes.get(i) + " + " + diff + " = " + n); return; } } } // Driver code public static void main (String[] args) { // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); } } // This code is contributed by mits
Python3
# Python3 program to implement Goldbach's # conjecture import math MAX = 10000; # Array to store all prime less # than and equal to 10^6 primes = []; # Utility function for Sieve of Sundaram def sieveSundaram(): # In general Sieve of Sundaram, produces # primes smaller than (2*x + 2) for a # number given number x. Since we want # primes smaller than MAX, we reduce # MAX to half. This array is used to # separate numbers of the form i + j + 2*i*j # from others where 1 <= i <= j marked = [False] * (int(MAX / 2) + 100); # Main logic of Sundaram. Mark all # numbers which do not generate prime # number by doing 2*i+1 for i in range(1, int((math.sqrt(MAX) - 1) / 2) + 1): for j in range((i * (i + 1)) << 1, int(MAX / 2) + 1, 2 * i + 1): marked[j] = True; # Since 2 is a prime number primes.append(2); # Print other primes. Remaining primes # are of the form 2*i + 1 such that # marked[i] is false. for i in range(1, int(MAX / 2) + 1): if (marked[i] == False): primes.append(2 * i + 1); # Function to perform Goldbach's conjecture def findPrimes(n): # Return if number is not even # or less than 3 if (n <= 2 or n % 2 != 0): print("Invalid Input"); return; # Check only upto half of number i = 0; while (primes[i] <= n // 2): # find difference by subtracting # current prime from n diff = n - primes[i]; # Search if the difference is also # a prime number if diff in primes: # Express as a sum of primes print(primes[i], "+", diff, "=", n); return; i += 1; # Driver code # Finding all prime numbers before limit sieveSundaram(); # Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); # This code is contributed # by chandan_jnu
C#
// C# program to implement Goldbach's conjecture using System; using System.Collections.Generic; class GFG { static int MAX = 10000; // Array to store all prime less // than and equal to 10^6 static List<int> primes = new List<int>(); // Utility function for Sieve of Sundaram static void sieveSundaram() { // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for // a number given number x. Since // we want primes smaller than MAX, // we reduce MAX to half This array is // used to separate numbers of the form // i + j + 2*i*j from others where 1 <= i <= j Boolean[] marked = new Boolean[MAX / 2 + 100]; // Main logic of Sundaram. Mark all numbers which // do not generate prime number by doing 2*i+1 for (int i = 1; i <= (Math.Sqrt(MAX) - 1) / 2; i++) for (int j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1) marked[j] = true; // Since 2 is a prime number primes.Add(2); // Print other primes. Remaining primes are of the // form 2*i + 1 such that marked[i] is false. for (int i = 1; i <= MAX / 2; i++) if (marked[i] == false) primes.Add(2 * i + 1); } // Function to perform Goldbach's conjecture static void findPrimes(int n) { // Return if number is not even or less than 3 if (n <= 2 || n % 2 != 0) { Console.WriteLine("Invalid Input "); return; } // Check only upto half of number for (int i = 0 ; primes[i] <= n / 2; i++) { // find difference by subtracting // current prime from n int diff = n - primes[i]; // Search if the difference is // also a prime number if (primes.Contains(diff)) { // Express as a sum of primes Console.WriteLine(primes[i] + " + " + diff + " = " + n); return; } } } // Driver code public static void Main (String[] args) { // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); } } /* This code contributed by PrinciRaj1992 */
PHP
<?php // PHP program to implement Goldbach's // conjecture $MAX = 10000; // Array to store all prime less than // and equal to 10^6 $primes = array(); // Utility function for Sieve of Sundaram function sieveSundaram() { global $MAX, $primes; // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a // number given number x. Since we want // primes smaller than MAX, we reduce // MAX to half. This array is used to // separate numbers of the form i + j + 2*i*j // from others where 1 <= i <= j $marked = array_fill(0, (int)($MAX / 2) + 100, false); // Main logic of Sundaram. Mark all // numbers which do not generate prime // number by doing 2*i+1 for ($i = 1; $i <= (sqrt($MAX) - 1) / 2; $i++) for ($j = ($i * ($i + 1)) << 1; $j <= $MAX / 2; $j = $j + 2 * $i + 1) $marked[$j] = true; // Since 2 is a prime number array_push($primes, 2); // Print other primes. Remaining primes // are of the form 2*i + 1 such that // marked[i] is false. for ($i = 1; $i <= $MAX / 2; $i++) if ($marked[$i] == false) array_push($primes, 2 * $i + 1); } // Function to perform Goldbach's conjecture function findPrimes($n) { global $MAX, $primes; // Return if number is not even // or less than 3 if ($n <= 2 || $n % 2 != 0) { print("Invalid Input \n"); return; } // Check only upto half of number for ($i = 0; $primes[$i] <= $n / 2; $i++) { // find difference by subtracting // current prime from n $diff = $n - $primes[$i]; // Search if the difference is also a // prime number if (in_array($diff, $primes)) { // Express as a sum of primes print($primes[$i] . " + " . $diff . " = " . $n . "\n"); return; } } } // Driver code // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); // This code is contributed by chandan_jnu ?>
Javascript
<script> // Javascript program to implement Goldbach's // conjecture let MAX = 10000; // Array to store all prime less than // and equal to 10^6 let primes = new Array(); // Utility function for Sieve of Sundaram function sieveSundaram() { // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a // number given number x. Since we want // primes smaller than MAX, we reduce // MAX to half. This array is used to // separate numbers of the form i + j + 2*i*j // from others where 1 <= i <= j let marked = new Array(parseInt(MAX / 2) + 100).fill(false); // Main logic of Sundaram. Mark all // numbers which do not generate prime // number by doing 2*i+1 for (let i = 1; i <= (Math.sqrt(MAX) - 1) / 2; i++) for (let j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1) marked[j] = true; // Since 2 is a prime number primes.push(2); // Print other primes. Remaining primes // are of the form 2*i + 1 such that // marked[i] is false. for (let i = 1; i <= MAX / 2; i++) if (marked[i] == false) primes.push(2 * i + 1); } // Function to perform Goldbach's conjecture function findPrimes(n) { // Return if number is not even // or less than 3 if (n <= 2 || n % 2 != 0) { document.write("Invalid Input <br>"); return; } // Check only upto half of number for (let i = 0; primes[i] <= n / 2; i++) { // find difference by subtracting // current prime from n let diff = n - primes[i]; // Search if the difference is also a // prime number if (primes.includes(diff)) { // Express as a sum of primes document.write(primes[i] + " + " + diff + " = " + n + "<br>"); return; } } } // Driver code // Finding all prime numbers before limit sieveSundaram(); // Express number as a sum of two primes findPrimes(4); findPrimes(38); findPrimes(100); // This code is contributed by gfgking </script>
Producción:
2 + 2 = 4 7 + 31 = 38 3 + 97 = 100
Un número de Goldbach es un número entero positivo que se puede expresar como la suma de dos números primos impares. Dado que cuatro es el único número par mayor que dos que requiere el primo par 2 para poder escribirse como la suma de dos primos, otra forma del enunciado de la conjetura de Goldbach es que todos los enteros pares mayores que 4 son números de Goldbach.
Este artículo es una contribución de Sahil Chhabra (akku) . 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 contribuido@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