数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究查找第 n 个幸运数
幸运数 - 对于给定的正整数 n，它是满足 pn# + m 为素数的最小整数 m > 1，其中 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 个幸运数。
示例 1
Input: n = 3
Output: 7
说明 - 前 3 个素数的乘积 -
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：素数阶乘方法
解决此问题的一个简单方法是首先计算 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() 中的 for 循环的复杂度为 O(nsqrt(n))。
空间复杂度 - O(1)
方法 2：埃拉托色尼筛法
埃拉托色尼筛法用于获取所有小于限制值的素数，我们将给它一个值 MAX。在这种方法中，我们创建一个布尔数组，所有条目都为 true，并将所有非素数索引标记为 false。然后将数组中的前 n 个素数相乘以获得前 n 个素数的乘积。然后类似于之前的方法，从 2 开始递增乘积以获取下一个素数。下一个素数与乘积之间的差值将是所需的幸运数。
伪代码
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 个素数相乘来找到素数阶乘。然后类似于之前的方法，找到 nextPrime。nextPrime 与乘积之间的差值是幸运数。
#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;
}
输出
15th Fortunate number : 107
时间复杂度 - O(n log(log(n)))
空间复杂度 - O(MAX)
结论
总之，可以通过以下两种方法找到第 n 个幸运数。
素数阶乘方法：找到前 n 个素数的乘积，并计算从该乘积开始的下一个素数。素数与乘积之间的差值是第 n 个幸运数。
埃拉托色尼筛法：找到所有小于限制值的素数，然后计算乘积和下一个素数以找到幸运数。
由于变量大小的限制，这两种方法仅对较小的 n 值有效。对于较大的值，需要更有效和优化的解决方案。
147 次查看
