資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用給定數字的數字構成所有質數
任何大於1的數，如果它不能寫成兩個較小自然數的乘積（除了1和它本身），則稱其為質數。例如，5是質數，因為它的唯一乘積形式1×5和5×1都包含5。正如素數定理所述，素數在數論中起著至關重要的作用，素數定理斷言任何大於1的自然數要麼本身是素數，要麼可以表示為素數的唯一乘積。該定理突出了素數在數學領域的重要性。
問題陳述
目標是確定可以使用長度為N的字串S中存在的數字生成的不同的質數的計數。
示例
輸入
S = “17”
輸出
3
解釋
可以使用S的數字生成的質數是
7 17 71
輸入
S = “1234”
輸出
15
解釋
可以使用S的數字生成的質數是
23 31 41 43 241 421 431 1243 1423 2143 2341 4231
輸入
S = “5”
輸出
1
解釋
可以使用S的數字生成的質數是
5
解決方案方法
一種可能的方法是識別可以使用給定數字中存在的數字構造的所有數字。我們迭代所有可能的數字組合，並檢查每個組合是否為質數。
演算法
將輸入數字讀取為字串。
初始化一個大小為10的數字陣列，以儲存輸入數字中每個數字的頻率。對字串中的字元進行迭代，然後更新遇到的每個數字的出現次數。
初始化一個空的無序質數集合，以儲存唯一的質數字符串。
建立一個名為“is_prime”的函式，該函式接受整數輸入“num”，如果“num”是質數，則返回true；否則，返回false。
如果num小於2，則返回false。
在2到“num”的平方根範圍內進行迭代，並驗證“num”是否能被此範圍內的任何數字整除。如果找到除數，則返回false。
如果num不能被範圍內的任何數字整除，則返回true。
定義一個遞迴函式generate_primes，它接受數字陣列、整數索引、整數num和無序質數集作為輸入。
如果索引等於10，則返回。
對於0到9範圍內的每個整數“i”，迭代執行以下步驟
如果digits[i]等於0，則繼續迭代。
透過將i連線到num的末尾來計算新的數字new_num。
如果new_num是質數，則將其字串表示形式新增到集合primes中。
遞減digits[i]。
使用digits、index+1、new_num和primes作為輸入遞迴呼叫generate_primes。
遞增digits[i]。
使用digits、0、0和primes作為輸入呼叫generate_primes，以使用輸入數字的數字生成所有可能的質數字符串。
列印集合primes的大小作為輸出。
示例：C++程式
給定一個正整數作為輸入，該程式旨在識別可以使用該數字中存在的數字生成的所有質數。它透過系統地迭代所有可能的數字組合並驗證每個組合的質數來實現這一點。該程式的輸出是使用輸入數字的數字可以形成的不同質數的計數。
示例
#include <iostream>
#include <unordered_set>
using namespace std;
// Function to check primality of a number
bool is_prime(int num) {
// Since 2 is the smallest prime number, if the number is less than 2, return false
if (num < 2) {
return false;
}
// Verify whether the number is divisible by any integer within the range of 2 to the square root of the number.
for (int i = 2; i*i <= num; i++) {
if (num % i == 0) {
return false;
}
}
// If the number is not divisible by any number from 2 to the square root of the number, it is prime
return true;
}
// Recursive function to generate all prime numbers using the given digits
void generate_primes(int digits[], int index, int num, unordered_set<string>& primes) {
// If all digits have been used, return
if (index >= 10) {
return;
}
// Generate all possible combinations of the digits
for (int i = 0; i < 10; i++) {
// If the digit has already been used up, skip it
if (digits[i] == 0) {
continue;
}
// Append the current digit to the number being generated
int new_num = num*10 + i;
// If the new number is prime, add it to the set of primes
if (is_prime(new_num)) {
primes.insert(to_string(new_num));
}
// Decrement the count of the current digit in the digits array
digits[i]--;
// Recursively generate all primes using the remaining digits and the new number
generate_primes(digits, index+1, new_num, primes);
// Increase the occurrence count of the current digit within the digits array for the purpose of backtracking.
digits[i]++;
}
}
int main() {
// Input number whose digits are used to generate primes
string number = "17";
cout << "Given number: " << number << endl;
// An array is utilized to store the frequency count of each digit present in the input number
int digits[10] = {0};
// Count the occurrences of each digit in the input number
for (char c : number) {
digits[c-'0']++;
}
// Set to store the unique prime numbers generated
unordered_set<string> primes;
// Generate all prime numbers using the digits and add them to the set of primes
generate_primes(digits, 0, 0, primes);
// Print the number of unique prime numbers generated
cout << "Number of unique prime numbers that can be formed using digits of a given number: ";
cout << primes.size() << endl;
return 0;
}
輸出
Given number: 17 Number of unique prime numbers that can be formed using digits of a given number: 3
當程式提供輸入數字17時，輸出將為3，這表示可以使用數字17中存在的數字構造三個質數，分別是7、17和71。
為了解釋程式的工作原理，它首先初始化一個大小為10的陣列，以儲存輸入數字中每個數字的頻率。在這種情況下，陣列將為[0, 1, 0, 0, 0, 0, 0, 1, 0, 0]，因為數字17中有一個7和一個1。
然後，程式使用遞迴函式生成所有可能的數字組合，並檢查每個組合是否為質數。在這種情況下，該函式將生成數字7、17和71。
生成的全部數字7、17和71都是質數。因此，程式產生一個輸出，指示可以使用輸入數字中找到的數字生成的不同的質數的總數，在這種情況下為3。
時間和空間複雜度分析
時間複雜度：O(10^n * sqrt(n))
is_prime(): O(sqrt(n))
generate_primes(): O(10^n * sqrt(n))，其中變數“n”表示輸入數字中存在的數字總數。這是因為，對於數字中的每個數字，我們有10個可能的選項（0-9），我們重複此過程n次。因此，我們生成的可能的組合總數為10^n。然後，我們使用is_prime函式檢查數字的質數性，這需要O(sqrt(num))時間。
空間複雜度：O(10^n + p)
generate_primes()函式佔用的輔助記憶體由於遞迴呼叫而為O(10^n)。無序集合物件primes也影響空間複雜度，它是O(p)，其中p是生成的質數的數量。
結論
本文探討了一種遞迴方法，用於計算可以使用表示為字串的給定數字的數字生成的質數的總數。我們討論了問題的概念、解決方案方法、演算法、C++程式以及時間和空間複雜度。
261 次瀏覽
