Find the nth lucky number

Lucky number - It is the smallest integer for which m > 1. For a given positive integer n, pn# m is a prime number, where pn# is the first n product primes.

For example, to calculate the third lucky number, first calculate the product of the first 3 prime numbers (2, 3, 5), which is 30. Adding 2 gives us 32, which is an even number, and adding 3 gives us 33, which is a multiple of 3. Integers up to 6 can also be excluded. Adding 7 gives us 37, which is a prime number. Therefore, 7 is the third lucky number.

The lucky number for the first original number is -

3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109….

Problem Statement

Given a number n. Find the nth lucky number.

Example 1

Input: n = 3

Output: 7

Explanation - Product of the first 3 price figures -

2  3  5 = 30
30 + 7 = 37, a prime number.

Example 2

Input: n = 7

Output: 19

Explanation - Product of the first 7 prime numbers -

2  3  5  7  11  13  17 = 510510
510510 + 19 = 510529, a prime number.

Method 1: Original method

A simple way to solve this problem is to first calculate pn#, the product of the first n prime numbers, and then find the difference between pn# and the next prime number. The difference obtained will be a lucky number.

pseudocode

procedure prime (num)
   if num <= 1
      ans = TRUE
   end if
   for i = 2 to sqrt(num)
      if i is a factor of num
         ans = false
      end if
   ans = true
end procedure
procedure nthFortunate (n)
   prod = 1
   count = 0
   for i = 2 to count < n
      if i is prime
         prod = prod * i
         count = count + 1
      end if
   nextPrime = prod + 2
   while nextPrime is not prime
      nextPrime = next Prime + 1
   ans = nextPrime - prod
end procedure

Example: C implementation

In the following program, the lucky number is calculated by calculating the primitive of the first n prime numbers and finding the next prime number after the primitive. The lucky number is the difference between the next prime number and the primitive number.

#include <bits/stdc++.h>
using namespace std;

// Function to find if a number is prime or not
bool prime(unsigned long long int num){
   if (num <= 1)
      return true;
   for (int i = 2; i <= sqrt(num); i++){
      if (num % i == 0)
         return false;
   }
   return true;
}

// Function to find the nth Fortunate number
unsigned long long int nthFortunate(int n){
   long long int prod = 1, count = 0;
   
   // Calculating product/primorial of first n prime numbers
   for (int i = 2; count < n; i++){
      if (prime(i)){
         prod *= i;
         count++;
      }
   }
   
   // Find the next prime greater than the product of n prime numbers
   unsigned long long int nextPrime = prod + 2;
   while (!prime(nextPrime)){
      nextPrime++;
   }
   
   // Fortunate number is the difference between prime and primorial
   unsigned long long int ans = nextPrime - prod;
   return ans;
}
int main(){
   int n = 15;
   cout << n << "th Fortunate number : " << nthFortunate(n);
   return 0;
}

Output

15th Fortunate number : 107

Time complexity - O(nsqrt(n)), where the complexity of the prime() function is O(sqrt(n)), and the complexity of the for loop in nthFortunate() is O(nsqrt(n)) .

Space complexity - O(1)

Method 2: Sieve of Eratosthenes

The Sieve of Eratosthenes is used to bring all prime numbers up to a limit, which will give us a value MAX. In this method, we create a boolean array containing all true entries and mark all non-prime indexes as false. Then multiply the first n prime numbers in the array to get the product of the first n prime numbers. Then similarly to the previous method, start at 2 and add 1 to the product to get the next prime number. The difference between the next prime number and the product is the required lucky number.

pseudocode

procedure nthFortunate (n)
   MAX is set
   prime[MAX] = {true}
   prime[0] = false
   prime[1] = false
   for i = 1 to i*i <= MAX
      if prime[i]
         for j = i*i to MAX with j = j + i in each iteration
            prime [j] = false
      end if
   prod = 1
   count = 0
   for i = 2 to count < n
      if prime[i]
         prod = prod * i
         count = count + 1
      end if
   nextPrime = prod + 2
   while nextPrime is not prime
      nextPrime = nextPrime + 1
   ans = nextPrime - prod
end procedure

Example: C implementation

In the following program, a Boolean prime array of size MAX records all prime numbers before MAX. The original is then found by multiplying the first n prime numbers. Then similar to the previous method, find nextPrime. The difference between nextPrime and Product is the lucky number.

#include <bits/stdc++.h>
using namespace std;

// Function to find the nth Fortunate number
unsigned long long int nthFortunate(int n){

   // Setting upper limit for Sieve of Eratosthenes
   const unsigned long long int MAX = 1000000000;
   vector<bool> prime(MAX, true);
   prime[0] = prime[1] = false;
   
   // Sieve of Eratosthenes to find all primes up to MAX
   for (unsigned long long int i = 2; i * i <= MAX; i++){
      if (prime[i]){
      
         // Setting all the multiples of i to false
         for (int j = i * i; j <= MAX; j += i){
            prime[j] = false;
         }
      }
   }
   
   // Find the first n primes and calculate their product
   unsigned long long int prod = 1, count = 0;
   for (unsigned long long int i = 2; count < n; i++){
      if (prime[i]){
         prod *= i;
         count++;
      }
   }
   
   // Find next prime greater than product
   unsigned long long int nextPrime = prod + 2;
   while (!prime[nextPrime])
      nextPrime++;
      
   // Fortunate number is difference between prime and product
   return nextPrime - prod;
}
int main(){
   int n = 25;
   cout << n << "th Fortunate number : " << nthFortunate(n);
   return 0;
}

Output

15th Fortunate number : 107

Time complexity - O(n log(log(n)))

Space complexity - O(MAX)

in conclusion

To sum up, the nth lucky number can be found in the following two ways.

Elementary method: Find the product of the first n prime numbers, and calculate the next prime number based on the product. The difference between the prime number and the product is the nth lucky number.

Sieve of Eratosthenes: Find all prime numbers that reach a certain limit, and then calculate the product with the next prime number to find the lucky number.

Both methods are valid for smaller values ​​of n simply due to variable size limitations. For larger values, more efficient and optimized solutions are required.

The above is the detailed content of Find the nth lucky number. For more information, please follow other related articles on the PHP Chinese website!