查詢第 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 值有效。對於較大的值,需要更有效和最佳化的解決方案。

更新於: 2023-07-25

147 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告