非素数只包含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

快速解决的一些建议。你知道吗

1. 生成一个数组arr，其中数字只有这些数字{2,3,5,7}
2. 使用预先计算好的数组is_prime使用筛子，这样会更快。你知道吗

3. 只使用arr（不是素数）中的有效值生成新数组

4. 在第3步生成的新数组中使用二进制搜索，使用a和b作为计数

Answer 2

正如@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)