python - 在 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 给我错误:

Process was terminated. It took longer than 12000ms to complete

Our servers are configured to only allow a certain amount of time for your code to execute. In rare cases the server may be taking on too much work and simply wasn't able to run your code efficiently enough. Most of the time though this issue is caused by inefficient algorithms. If you see this error multiple times you should try to optimize your code further.

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

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

并检查它们是否是质数。我敢打赌它会快得多。