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

快速解决的一些建议。

生成数组 arr 其中数字只有这些数字 {2,3,5,7}
使用预先计算的数组 is_prime 使用筛子，这样会更快。
生成一个新数组，其中只有 arr 中的有效值（不是素数）
在第 3 步生成的新数组中使用二进制搜索，使用 a 和 b 进行计数

Answer 2

正如@ArjunSingh 所建议的，首先创建一个只有数字 {2,3,5,7} 的数组。它还 returns 只是 [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

针对以 2 或 5 结尾的数字将 is_prime 函数优化为 return 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)

非素数只包含2,3,5,7优化

Not prime numbers contains only 2,3,5,7 optimization

python

algorithm

performance

primes

python-3.x