幸运数字 - 它是 m > 1 的最小整数，对于给定的正整数 n，pn# + m 是素数，其中 pn# 是第一个 n 的乘积质数。
例如，要计算第三个幸运数字，首先计算前 3 个素数 (2, 3, 5) 的乘积，即 30。加 2 后得到 32，这是偶数，加 3 得到 33，是 3 的倍数。同样可以排除 6 以内的整数。加上 7 得到 37，这是一个素数。因此，7是第三个幸运数字。
第一个原初数的幸运数字是 -
3, 5, 7, 13, 23, 17, 19, 23, 37, 61, 67, 61, 71, 47, 107, 59, 61, 109 ….
问题陈述给定一个数字n。找到第 n 个幸运数字。
示例 1input: n = 3
output: 7
解释 - 前 3 个价格数字的乘积 -
2 3 5 = 3030 + 7 = 37, a prime number.
示例 2input: n = 7
output: 19
解释 - 前 7 个素数的乘积 -
2 3 5 7 11 13 17 = 510510510510 + 19 = 510529, a prime number.
方法一：原始方法解决该问题的一个简单方法是首先计算 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 = trueend procedureprocedure 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 - prodend procedure
示例：c++ 实现在下面的程序中，通过计算前n个素数的本初以及找到本初后的下一个素数来计算幸运数。幸运数是下一个素数与本初数之间的差。
#include <bits/stdc++.h>using namespace std;// function to find if a number is prime or notbool 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 numberunsigned 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() 中的 for 循环的复杂度为 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 - prodend procedure
示例：c++ 实现在下面的程序中，大小为 max 的布尔素数数组记录了 max 之前的所有素数。然后通过将前 n 个素数相乘来找到原初。然后与之前的方法类似，找到nextprime。 nextprime 和 product 的区别在于幸运数字。
#include <bits/stdc++.h>using namespace std;// function to find the nth fortunate numberunsigned 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;}
输出15th fortunate number : 107

时间复杂度 - o(n log(log(n)))
空间复杂度 - o(max)
结论综上所述，第n个幸运数可以通过以下两种方式找到。
初等方法：求前n个素数的乘积，并根据乘积计算下一个素数。质数与乘积之差是第 n 个幸运数。
埃拉托斯特尼筛法：找出所有达到某个极限的素数，然后计算与下一个素数的乘积，从而找到幸运数。
仅由于变量大小的限制，这两种方法对于较小的 n 值都是有效的。对于更大的值，需要更高效和优化的解决方案。
以上就是找到第n个幸运数的详细内容。