我可能很快会写一篇完整的关于生成质数的算法的文章，因为这是一个很酷的话题，本身也是一个古老的研究领域。最广为人知的算法是爱拉托逊斯筛法（Sieve of Erathosthenes ），但这只是冰山一角。[注6]
在这里，一个非常幼稚的实现就够了：
def primes(starting: int = 2): """Yield the primes in order.
Args: starting: sets the minimum number to consider.
Note: `starting` can be used to get all prime numbers _larger_ than some number. By default it doesn't skip any candidate primes. """ candidate_prime = starting while True: candidate_factor = 2 is_prime = True # We'll try all the numbers between 2 and # candidate_prime / 2. If any of them divide # our candidate_prime, then it's not a prime! while candidate_factor <= candidate_prime // 2: if candidate_prime % candidate_factor == 0: is_prime = False break candidate_factor += 1 if is_prime: yield candidate_prime candidate_prime += 1
创建空列表
def empty_list() -> int: """Create a new empty list.""" # 1 is the empty list. It isn't divisible by any prime. return 1
遍历元素
def iter_list(l: int): """Yields elements in the list, from first to last.""" # We go through each prime in order. The next value of # the list is equal to the number of times the list is # divisible by the prime. for p in primes(): # We decided we will have no trailing 0s, so when # the list is 1, it's over. if l <= 1: break # Count the number of divisions until the list is # not divisible by the prime number. num_divisions = 0 while l % p == 0: num_divisions += 1 l = l // p # could be / as well yield num_divisions
访问元素
def access(l: int, i: int) -> int: """Return i-th element of l.""" # First we iterate over all primes until we get to the # ith prime. j = 0 for p in primes(): if j == i: ith_prime = p break j += 1 # Now we divide the list by the ith-prime until we # cant divide it no more. num_divisions = 0 while l % ith_prime == 0: num_divisions += 1 l = l // ith_prime return num_divisions
添加元素
def append(l: int, elem: int) -> int: # The first step is finding the largest prime factor. # We look at all primes until l. # The next prime after the last prime factor is going # to be the base we need to use to append. # E.g. if the list if 18 -> 2**1 * 3**2 -> [1, 2] # then the largest prime factor is 3, and we will # multiply by the _next_ prime factor to some power to # append to the list. last_prime_factor = 1 # Just a placeholder for p in primes(): if p > l: break if l % p == 0: last_prime_factor = p # Now get the _next_ prime after the last in the list. for p in primes(starting=last_prime_factor + 1): next_prime = p break # Now finally we append an item by multiplying the list # by the next prime to the `elem` power. return l * next_prime ** elem
