資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
