Dado un número entero N , la tarea es imprimir los primeros N términos del Número de Kummer .
Ejemplos:
Entrada: N = 3
Salida: 1, 5, 29
1 = -1 + 2
5 = -1 + 2 * 3
29 = -1 + 2 * 3 * 5
Entrada: N = 5
Salida: 1, 5, 29, 209 , 2309
Un enfoque ingenuo es verificar que todos los números del 1 al n uno por uno sean primos o no, en caso afirmativo, almacene la multiplicación en el resultado, almacene de manera similar el resultado de la multiplicación de primos hasta n y agregue -1.
El enfoque eficiente es encontrar todos los números primos hasta n usando la criba de Sundaram y luego simplemente calcular el n-ésimo número de kummer multiplicándolos todos y sumando -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find Kummer // number upto n terms #include <bits/stdc++.h> using namespace std; const int MAX = 1000000; // vector to store all prime // less than and equal to 10^6 vector<int> primes; // Function for the Sieve of Sundaram. // This function stores all // prime numbers less than MAX in primes 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+2ij from others // where 1 <= i <= j bool marked[MAX / 2 + 1] = { 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 += 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 calculate nth Kummer number int calculateKummer(int n) { // Multiply first n primes int result = 1; for (int i = 0; i < n; i++) result = result * primes[i]; // return nth Kummer number return -1 + result; } // Driver code int main() { int n = 5; sieveSundaram(); for (int i = 1; i <= n; i++) cout << calculateKummer(i) << ", "; return 0; }
Java
// Java program to find Kummer // number upto n terms import java.util.*; class GFG{ static int MAX = 1000000; // vector to store all prime // less than and equal to 10^6 static Vector<Integer> primes = new Vector<Integer>(); // Function for the Sieve of Sundaram. // This function stores all // prime numbers less than MAX in primes 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+2ij from others // where 1 <= i <= j boolean marked[] = new boolean[MAX / 2 + 1]; // 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 += 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 calculate nth Kummer number static int calculateKummer(int n) { // Multiply first n primes int result = 1; for (int i = 0; i < n; i++) result = result * primes.get(i); // return nth Kummer number return -1 + result; } // Driver code public static void main(String[] args) { int n = 5; sieveSundaram(); for (int i = 1; i <= n; i++) System.out.print(calculateKummer(i) + ", "); } } // This code is contributed by sapnasingh4991
Python3
# Python3 program to find Kummer # number upto n terms import math MAX = 1000000 # list to store all prime # less than and equal to 10^6 primes=[] # Function for the Sieve of Sundaram. # This function stores all # prime numbers less than MAX in primes 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 list is used to separate # numbers of the form # i+j+2ij from others # where 1 <= i <= j marked = [ 0 ] * int(MAX / 2 + 1) # 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, 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, MAX // 2 + 1 ): if (marked[i] == False): primes.append(2 * i + 1) # Function to calculate nth Kummer number def calculateKummer(n): # Multiply first n primes result = 1 for i in range(n): result = result * primes[i] # return nth Kummer number return (-1 + result) # Driver code # Given N N = 5 sieveSundaram() for i in range(1, N + 1): print(calculateKummer(i), end = ", ") # This code is contributed by Vishal Maurya
C#
// C# program to find Kummer // number upto n terms using System; using System.Collections.Generic; class GFG{ static int MAX = 1000000; // vector to store all prime // less than and equal to 10^6 static List<int> primes = new List<int>(); // Function for the Sieve of Sundaram. // This function stores all // prime numbers less than MAX in primes 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+2ij from others // where 1 <= i <= j bool []marked = new bool[MAX / 2 + 1]; // 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 += 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 calculate nth Kummer number static int calculateKummer(int n) { // Multiply first n primes int result = 1; for (int i = 0; i < n; i++) result = result * primes[i]; // return nth Kummer number return -1 + result; } // Driver code public static void Main(String[] args) { int n = 5; sieveSundaram(); for (int i = 1; i <= n; i++) Console.Write(calculateKummer(i) + ", "); } } // This code is contributed by 29AjayKumar
Javascript
<script> // JavaScript program to find Kummer // number upto n terms // Function to count the number of // ways to decode the given digit // sequence let MAX = 1000000; // vector to store all prime // less than and equal to 10^6 let primes = []; // Function for the Sieve of Sundaram. // This function stores all // prime numbers less than MAX in primes 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+2ij from others // where 1 <= i <= j let marked = Array.from( {length: MAX / 2 + 1}, (_, i) => 0); // 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 += 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 calculate nth Kummer number function calculateKummer(n) { // Multiply first n primes let result = 1; for (let i = 0; i < n; i++) result = result * primes[i]; // return nth Kummer number return -1 + result; } // Driver Code let n = 5; sieveSundaram(); for (let i = 1; i <= n; i++) document.write(calculateKummer(i) + ", "); </script>
1, 5, 29, 209, 2309,
Referencias: https://oeis.org/A057588