C++ 找到第n个幸运数

幸运数 是最小的大于1的整数m，满足对于给定的正整数n，pn# + m是一个素数，其中pn#是前n个素数的乘积。

例如，要计算第三个幸运数，首先计算前三个素数（2、3、5）的乘积，即30。加上2得到32，这是一个偶数，加上3得到33，这是3的倍数。类似地，可以排除掉小于等于6的整数。加上7得到37，这是一个素数。因此，7是第三个幸运数。

前n个素数的幸运数为-

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

问题陈述

给定一个数n，找到第n个幸运数。

示例1

Input: n = 3

Output: 7

解释 −前三个价格数字的乘积−

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

示例2

Input: n = 7

Output: 19

说明 - 前7个质数的乘积 –

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

方法1：Primorial算法

解决这个问题的简单方法是首先计算pn#，即前n个质数的乘积，然后找到pn#与下一个质数的差值。得到的差值将是一个幸运数。

伪代码

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

示例：C++实现

在下面的程序中，通过计算前n个质数的原根和找到原根后的下一个质数来计算幸运数。幸运数是下一个质数和原根的差值。

#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;
}

输出

15th Fortunate number : 107

时间复杂度-O(nsqrt(n)),其中prime()函数的复杂度为O(sqrt(n))，nthFortunate()中的循环复杂度为O(nsqrt(n))。

空间复杂度-O(1)

方法2：埃拉托斯特尼筛法

埃拉托斯特尼筛法用于获取小于等于给定值MAX的所有素数。在这种方法中，我们创建一个布尔数组，所有元素都设为true，并将所有非素数的索引设为false。然后将数组中的前n个素数相乘，得到前n个素数的乘积。接着类似于之前的方法，从2开始每次将乘积加1，直到得到下一个素数。下一个素数与乘积之间的差值就是所需的幸运数。

伪代码

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

示例：C++ 实现

在下面的程序中，大小为 MAX 的布尔素数数组记录了所有小于 MAX 的素数。然后通过乘积前 n 个素数找到了 primorial。然后，类似于之前的方法，找到了 nextPrime。nextPrime 和 product 之间的差异就是幸运数。

#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;
}