在 Python 中查找总素数(进程终止错误)

Question

这是我正在解决的问题。

数字23 是唯一的，因为它的所有数字都是质数。此外，它本身就是一个素数。10 到 100 之间有 4 个这样的数字：23、37、53、73。我们称这些数字为"总素数"。

完成取范围[a, b)并返回该范围内总素数数数的函数 (a <= primes < b)。测试范围高达 10^7。

示例：
(10， 100) ==> 4 # [23， 37， 53， 73](500， 600) ==> 3 # [523， 557， 577]

我尝试这样解决(它返回样本测试的正确数字)：

def isPrime(n):
if n < 2: return False
for x in range(2, int(n**0.5) + 1):
if n % x == 0:
return False
return True
def itsDigits(n):
for i in set(str(n)):
if not isPrime(int(i)):
return False
return True
def get_total_primes(a, b):
count=0
for i in range(a,b):
if(isPrime(i) and itsDigits(i)):
count+=1
return count

但是Codewars给了我一个错误：

进程已终止。完成时间超过12000毫秒

我们的服务器配置为仅允许一定的时间 要执行的代码。在极少数情况下，服务器也可能承担 很多工作，根本无法足够有效地运行代码。 大多数情况下，这个问题是由效率低下的 算法。如果您多次看到此错误，则应尝试 进一步优化您的代码。

你能帮我优化我的代码吗？

Answer 1

正如评论中所建议的，也许正确的方法是先只从质数中生成数字，然后检查这些是否是素数？您可以使用生成器表达式轻松生成给定长度的{2， 3， 5， 7}的所有可能组合，如下所示：

def prime_digit_combinations(length):
if length <= 0:
return [0]
return ((10 ** (length - 1)) * current + rest
for current in [2, 3, 5, 7]
for rest in prime_digit_combinations(length - 1))

之后，您只需生成所有大于a且小于b的组合，例如：

def get_possible_total_primes(a, b):
result = []
for length in range(len(str(a)), len(str(b)) + 1):
result.extend(
num for num in prime_digit_combinations(length)
if a <= num <= b
)
return result

并检查这些是否是主要的。我敢打赌它会快得多。