python - 非质数只包含 2,3,5,7 优化

Question

任务是:

You are given two positive integers a and b (b - a <= 20000). Complete the function which returns a list of all those numbers in the interval [a, b) whose digits are made up of prime numbers (2, 3, 5, 7) but which are not primes themselves.

Be careful about your timing!

我的解决方案是:

def not_primes(a, b):
    def is_prime(n):
        if not n % 2 and n > 2:
            return False

        return all(n % i for i in range(3, int(n ** 0.5) + 1, 2))

    arr = [x for x in range(a, b) if all(i in {'2', '3', '5', '7'} for i in str(x))]
    return [x for x in arr if not is_prime(x)]

这个想法就像是对值进行预排序，并验证是否仅由 2、3、5 或 7 组成的数字是素数。

但对于大范围来说它很慢，而且很多测试都很慢。

提高性能的更好方法是什么？

Answer 1

正如@ArjunSingh 所建议的，首先创建一个只有数字 {2,3,5,7} 的数组。它还仅返回 [a,b] 范围内的数字。

def interval(a, b):
    values = {0: [2,3,5,7]}
    magnitude = 1
    for r in range(1,10):
        magnitude *= 10
        values[r] = []
        for digit in values[0]:
            for value in values[r-1]:
                n = digit*magnitude + value
                if n <= b:
                    values[r].append(n)
                    continue
                return [v for r1 in range(1,r+1) for v in values[r1] if v >= a]
    return None    # b is outside of the range 10**10

优化 is_prime 函数以对以 2 或 5 结尾的数字返回 False。

def is_prime(n):
    if n % 10 in [2,5]:
        return False
    return all(n % i for i in range(3, int(n ** 0.5) + 1, 2))

现在我们得到区间内的值，只打印那些不是素数的值。

a = 220000
b = 240000
for i in interval(a,b):
    if not is_prime(i):
        print(i)