C++ 计算一个给定数字的所有可以由数字组成的质数

任何大于1的数字被说成是质数，如果它不能被两个比它小的自然数的乘积表示，除非这两个自然数分别为1和这个数字本身。例如，5是质数，因为它的唯一的乘积形式，1 5和5 1，都含有5。质数在数论中扮演着重要角色，正如所述的质数定理，它断言任何大于1的自然数要么是质数本身，要么可以被唯一质数的乘积表示。这个定理突出了质数在数学领域中的重要性。

问题陈述

目标是确定利用字符串S中的数字能生成的不同质数的数量，S的长度为N。

示例例子

输入

S = “17”

输出

解释

从S的数字中可以生成的质数有：

7 17 71

输入

S = “1234”

输出

解释

可以从S的数字中生成的质数有：

23 31 41 43 241 421 431 1243 1423 2143 2341 4231

输入

S = “5”

输出

解释

可从字符串S的数字生成的质数为

解决方案方法

一个潜在的方法是识别出可以利用给定数字中的数字构造的所有数字。我们遍历所有可能的数字组合，并检查每个组合是否为质数。

算法

将输入数字读为字符串。
初始化大小为10的数字数组，用于存储输入数字中每个数字的频率。对字符串中的字符进行迭代，并随后更新遇到的每个数字的发生次数。
初始化一个空的无序集合来存储唯一的质数字符串。
创建一个名为“is_prime”的函数，该函数接受整数输入“num”，如果“num”是质数，则返回true；否则，返回false。
- 如果num小于2，则返回false。
- 对范围从2到“num”的平方根进行迭代，并验证“num”是否可被此范围内的任何数整除。如果找到一个除数，则返回false。
- 如果num在范围内不可被任何数整除，则返回true。
定义一个递归函数generate_primes，该函数接受数字数组，整数索引，整数num和无序集合primes作为输入。
- 如果索引等于10，则返回。
- 对于范围从0到9的每个整数“i”，依次执行以下步骤：
- 如果digits[i]等于0，则继续迭代。
- 通过将i连接到num的末尾来计算新数字new_num。
- 如果new_num是质数，则将其字符串表示添加到集合primes中。
- 将digits[i]减一。
- 调用generate_primes递归地将digits，index+1，new_num和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))的时间。