幸運數字 - 它是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 個幸運數字。
Input: n = 3
Output: 7
解釋 - 前 3 個價格數字的乘積 -
2 3 5 = 30 30 + 7 = 37, a prime number.
Input: n = 7
Output: 19
解釋 - 前 7 個質數的乘積 -
2 3 5 7 11 13 17 = 510510 510510 + 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 = 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
在下面的程式中,透過計算前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)
埃拉托色尼篩用於將所有質數達到一個極限,我們將給出一個值 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
在下面的程式中,大小為 MAX 的布林素數數組記錄了 MAX 之前的所有質數。然後透過將前 n 個質數相乘來找到原初。然後與之前的方法類似,找到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; }
15th Fortunate number : 107
時間複雜度 - O(n log(log(n)))
空間複雜度 - O(MAX)
綜上所述,第n個幸運數可以透過以下兩種方式找到。
初等方法:求前n個質數的乘積,並根據乘積計算下一個質數。質數與乘積之差是第 n 個幸運數。
埃拉托斯特尼篩法:找出所有達到某個極限的質數,然後計算與下一個質數的乘積,從而找到幸運數。
僅由於變數大小的限制,這兩種方法對於較小的 n 值都是有效的。對於更大的值,需要更有效率和最佳化的解決方案。
以上是找到第n個幸運數的詳細內容。更多資訊請關注PHP中文網其他相關文章!