P204: A list of prime numbers

求指指定区间内所有的质数。比如，给定区间10至20应返回所有大于等10且小于等20的质数[11, 13, 17, 19]。照例先写测试用例：

在P201中已经实现了一个检验一个整数是否为质数的方法is_prime。现在，给定一个整数区问求其中所有的质数。则最简单的方法就是逐个检验区间内所有整数。（检验质数的方法请参见P201）。

完整的代码实现：

代码中使用了Python的一个特性yield。了解yield之前要先了解「生成器（generator）」，而要了解生成器则要先了解「可迭代（iterable）」。

Iterables

「可迭代对象（iterable objects）」是实现了__iter__()的对象，__iter__()应该返回一个「迭代器（iterator）」对象。 迭代器器是一个实现了next()的对象，next()应该返回可迭代对象中下一个元素，当没有更多元素时则抛出异常StopIteration。 最简单的用例就是可迭代对自己实现next()然后把自己作为迭代器在__iter__()中返回。 可迭代对象可以被用于for循环中，也可以用以构造列表。^{python-wiki-iterator}

Generator

「生成器（generator）」是「迭代器（iterator）」的一种实现。其实现了__iter__()和next()。

Yield expressions

Yield表达式用于定义生成器函数或异步生成器函数（asynchronous generator function），所以其祇能在函数体定义中使用。在函数体中使用yield表达式会使该函数变成一个生成器，在用关键词async def定义的函数体中使用则会使协程函数变成异步生成器。^{python-doc-yieldexpr}

本例中，我们使用yield表达式将函数prime_generator转换成一个生成器。生成器与列表及其它有序容器的区别就是：生成器中的元素是在被访问时才构造的；而列表中的元素则是在定义列表时就构造了。

请看如下代码，prime_list在找出区间内所有的质数并放在列表中返回。执行代码后就能发现，其先执行prime_list中所有代码（Check 1, Check 2, ..., Check 10），然后再执行for x in prime_list(1, 10)循环（Iterate 2, Iterate 3, ..., Iterate 7）。

from python99.arithmetic.p201 import is_prime

def prime_list(lower, upper):
    result = []
    for num in range(lower, upper+1):
        print("Check "+str(num))
        if is_prime(num):
            print("Found prime "+str(num))
            result.append(num)
    return result

for x in prime_list(2,10):
    print("Iterate "+str(x))

控制台输出：

Check 2
Found prime 2
Check 3
Found prime 3
Check 4
Check 5
Found prime 5
Check 6
Check 7
Found prime 7
Check 8
Check 9
Check 10
Iterate 2
Iterate 3
Iterate 5
Iterate 7

再看如下代码，prime_generator使用yield返回质数结果，这使用prime_generator变成一个生成器。执行代码后发现，prime_generator不会在for x in prime_generator(2, 10)之前就构造所有元素。而是当外部访问一个元素（调用next()）时再生成。比如，当外部要访问第一个元素时，其逐个检验区间内的整数，当找到第一个质数时（Found prime 2）就立马返回该元素，而不是像list一样构造完所有元素后才返回。

from python99.arithmetic.p201 import is_prime

def prime_generator(lower, upper):
    for num in range(lower, upper+1):
        print("Check "+str(num))
        if is_prime(num):
            print("Found prime "+str(num))
            yield num

for x in prime_generator(2,10):
    print("Iterate "+str(x))

控制台输出：

Check 2
Found prime 2
Iterate 2
Check 3
Found prime 3
Iterate 3
Check 4
Check 5
Found prime 5
Iterate 5
Check 6
Check 7
Found prime 7
Iterate 7
Check 8
Check 9
Check 10

在「祇要求给出一个可行解」的应用中使用生成器可以减少不必要的运算。「在祇要求给出一个可行解」的应用中，不需要枚举所有值。生成器「按需构造」的特性很适用。

is_prime代码实现：

参考文献

^{python-wiki-iterator}. https://wiki.python.org/moin/Iterator ↩

^{python-doc-yieldexpr}. https://docs.python.org/3.7/reference/expressions.html#yieldexpr ↩