Given an integer N, the task is to print the first N terms of the Kummer Number.
Examples:
Input: N = 3
Output: 1, 5, 29
1 = -1 + 2
5 = -1 + 2 * 3
29 = -1 + 2 * 3 * 5
Input: N = 5
Output: 1, 5, 29, 209, 2309
A Naive Approach is to check all numbers from 1 to n one by one is prime or not, if yes then store the multiplication in result, similarly store the result of multiplication of primes till n and add -1.
Efficient Approach is to find all the prime up-to n using Sieve of Sundaram and then just calculate the nth kummer number by multiplying them all and adding -1.
Below is the implementation of the above approach:
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^6vector<int> primes;// Function for the Sieve of Sundaram.// This function stores all// prime numbers less than MAX in primesvoid 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 numberint 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 codeint 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 termsimport java.util.*;class GFG{static int MAX = 1000000; // vector to store all prime// less than and equal to 10^6static Vector<Integer> primes = new Vector<Integer>(); // Function for the Sieve of Sundaram.// This function stores all// prime numbers less than MAX in primesstatic 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 numberstatic 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 codepublic 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 termsimport mathMAX = 1000000# list to store all prime# less than and equal to 10^6primes=[]# Function for the Sieve of Sundaram.# This function stores all# prime numbers less than MAX in primesdef 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 numberdef 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 NN = 5sieveSundaram()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 termsusing System;using System.Collections.Generic;class GFG{static int MAX = 1000000;// vector to store all prime// less than and equal to 10^6static List<int> primes = new List<int>();// Function for the Sieve of Sundaram.// This function stores all// prime numbers less than MAX in primesstatic 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 numberstatic 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 codepublic 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^6let primes = []; // Function for the Sieve of Sundaram.// This function stores all// prime numbers less than MAX in primesfunction 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 numberfunction 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> |
Output:
1, 5, 29, 209, 2309,
1, 5, 29, 209, 2309,
References: https://oeis.org/A057588
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
