GESP三级 - 求无暇素数 - C++ 算法详解

{"title":"GESP三级 - 求无暇素数 - C++ 算法详解","description":"本题要求找出给定数字字符串中所有组成的无暇素数，即本身为素数，交换个位和十位数字后仍然为素数的数字。文章提供详细的 C++ 代码实现、复杂度分析以及优化建议，帮助您更好地理解并解决此算法问题。","keywords":"GESP, 三级, 算法, 素数, 无暇素数, C++, 递归, 全排列, 复杂度分析, 优化","content":" 思路：\n\n1. 首先需要判断一个数是否为素数。可以写一个函数isPrime()来判断。\n2. 对于给定的数字字符串，可以使用递归的方式进行全排列，将所有可能的组合生成。\n3. 对于每一个生成的组合，判断其是否为无暇素数，如果是则输出。\n\n代码实现：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <string>\n#include <algorithm>\n#include <cmath>\nusing namespace std;\n\nbool isPrime(int n) {\n if (n == 2) return true;\n if (n < 2 || n % 2 == 0) return false;\n int sqrt_n = sqrt(n);\n for (int i = 3; i <= sqrt_n; i += 2) {\n if (n % i == 0) return false;\n }\n return true;\n}\n\nvoid findFlawlessPrimes(string digits, string curr, vector<string>& result) {\n if (digits.empty()) {\n int num = stoi(curr);\n if (isPrime(num)) {\n result.push_back(curr);\n }\n return;\n }\n for (int i = 0; i < digits.length(); i++) {\n string newDigits = digits;\n string newCurr = curr + digits[i];\n newDigits.erase(i, 1);\n findFlawlessPrimes(newDigits, newCurr, result);\n }\n}\n\nint main() {\n string digits;\n cin >> digits;\n vector<string> result;\n findFlawlessPrimes(digits, "", result);\n for (int i = 0; i < result.size(); i++) {\n cout << result[i];\n if (i < result.size() - 1) {\n cout << ",";\n }\n }\n return 0;\n}\n\n\n复杂度分析：\n\n1. 对于每个数字字符串，需要进行全排列，时间复杂度为O(n!)，其中n为字符串长度。\n2. 对于每个生成的组合，需要判断其是否为素数，时间复杂度为O(sqrt(m))，其中m为组合的位数。\n3. 总体时间复杂度为O(n! * sqrt(m))。\n\n空间复杂度分析：\n\n1. 需要一个vector来存储所有的无暇素数，空间复杂度为O(n!)。\n2. 递归调用时，需要O(n)的栈空间。\n3. 总体空间复杂度为O(n!)。\n\n优化建议：\n\n1. 由于素数判断的效率影响很大，可以考虑使用埃拉托斯特尼筛法预先计算一定范围内的素数，并在判断时直接查询。\n2. 在递归调用中，可以记录已经生成的素数，避免重复计算。\n3. 对于较长的数字字符串，可以考虑使用剪枝策略，例如，如果一个组合的前两位数字不是素数，则直接跳过该组合。\n\n总结：\n\n本题是一个经典的组合问题，需要使用递归和全排列的方法来解决。代码实现中要注意优化素数判断的效率，并根据实际情况使用剪枝策略来提高算法效率。