python - 打印给定间隔的素数反转列表

Question

所以我想出了如何以给定间隔的反向形式打印所有素数，但是对于测试用例，当他们将下限设置为 1 时，它也会打印它。我们知道1不是素数。

我的代码是:

def prime_list_reversed(x, y):
"""
Input: the number x and y
Output: all prime numbers within [x,y] in reverse order

>>> prime_list_reversed(3, 10)
[7, 5, 3]
>>> prime_list_reversed(3, 3)
[3]
>>> prime_list_reversed(2, 2)
[2]
"""
assert type(x) == int, "first argument must be an integer"
assert type(y) == int, "second argument must be an integer"
assert x > 1, "1 is not a prime number"
assert y >= x,  "second argument must be >= the first one"

# YOUR CODE IS HERE #
lst = []
for i in range(x, y + 1):
    for c in range(2, i):
        if (i % c) == 0:
            break
    else:
        lst.append(i)
return list(reversed(lst))

一个测试用例

prime_list_reversed(1, 3)
[3,2,1]

Answer 1

您的素数检查器将为 i=1 构造 range(2, 1)，但该范围为空。确实:

>>> list(range(2, 1))
[]

这意味着没有对i=1进行检查，因此您的程序认为它是素数。我们可以在这里做两件事:

1. 检查 if 语句是否 i == 1 以避免发出；
2. 首先确保外部范围永远不会发出 1。

def prime_list_reversed(x, y):
    # ...
    lst = []
    for i in range(<b>max(2, x)</b>, y + 1):
        for c in range(2, i):
            if (i % c) == 0:
                break
        else:
            lst.append(i)
    return list(reversed(lst))

上面解决了问题，但是不是很优雅:我们先构造一个列表，然后反转列表。我们也可以简单地反向发射元素:

def prime_list_reversed(x, y):
    # ...
    lst = []
    for i in range(<b>y, max(2, x) - 1, -1</b>):
        for c in range(2, i):
            if (i % c) == 0:
                break
        else:
            lst.append(i)
    return <b>lst</b>

现在我们以相反的方式产生元素。但代码仍然效率低下:我们测试所有偶数。但测试一个数字是否可以被 2 整除就足够了，如果不能，我们可以省略对 4、6 等的检查。因为如果它不能被 2 整除，那么它肯定不能被 4、6 整除。而不是检查一个数字是否可以被 2

整除

def prime_list_reversed(x, y):
    # ...
    lst = []
    for i in range(y <b>- (~y & 1)</b>, max(3, x) - 1, <b>-2</b>):
        for c in range(<b>3, i, 2</b>):
            if (i % c) == 0:
                break
        else:
            lst.append(i)
    if x <= 2 < y:
        lst.append(2)
    return lst

但它仍然可以提高效率。如果一个数a能被b整除，我们就知道有一个c = a/b。这意味着如果b >√a，则c≤√a。我们可以利用这个属性:检查√i就足够了，因为我们知道否则我们已经通过其他部门测试了它:

from math import ceil, sqrt

def prime_list_reversed(x, y):
    # ...
    lst = []
    for i in range(y - (~y & 1), max(3, x) - 1, <b>-2</b>):
        for c in range(3, <b>ceil(sqrt(i))+1</b>, 2):
            if not i % c:
                break
        else:
            lst.append(i)
    if x <= 2 < y:
        lst.append(2)
    return lst

最后，通常最好将其设为生成器，因为这允许我们懒惰例如获取前 10 个元素:

from math import ceil, sqrt

def prime_list_reversed(x, y):
    # ...
    for i in range(y - (~y & 1), max(3, x) - 1, <b>-2</b>):
        for c in range(3, ceil(sqrt(i))+1, 2):
            if not i % c:
                break
        else:
            <b>yield i</b>
    if x <= 2 < y:
        <b>yield 2</b>

然后我们获得1和500之间的范围:

>>> list(prime_list_reversed(1, 500))
[499, 491, 487, 479, 467, 463, 461, 457, 449, 443, 439, 433, 431, 421, 419, 409, 401, 397, 389, 383, 379, 373, 367, 359, 353, 349, 347, 337, 331, 317, 313, 311, 307, 293, 283, 281, 277, 271, 269, 263, 257, 251, 241, 239, 233, 229, 227, 223, 211, 199, 197, 193, 191, 181, 179, 173, 167, 163, 157, 151, 149, 139, 137, 131, 127, 113, 109, 107, 103, 101, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2]