质数发生器解释? [英] Prime numbers generator explanation?

问题描述

我正在寻找一种生成素数的算法.我发现以下由罗伯特·威廉·汉克斯(Robert William Hanks)完成的任务.它非常有效，并且比其他算法更好，但我无法理解其背后的数学原理.

I was searching for an algorithm to generate prime numbers. I found the following one done by Robert William Hanks. It is very efficient and better than the other algorithms but I can not understand the math behind it.

def primes(n):
    """ Returns  a list of primes < n """
    lis = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if lis[i]:
            lis[i*i::2*i]=[False]*int((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in range(3,n,2) if lis[i]]

True值的数组和最终质数数组之间的关系是什么?

What is the relation between the array of Trues values and the final prime numbers array?

推荐答案

从数组中的 n True值开始，逐步将i从3枚举为sqrt(n)的2，如果数组中的第 i 个条目仍为True，则将所有从i^2到数组末尾的条目设置为2*i到False(这些将是i的倍数).

Starting with n True values in an array, with i enumerated from 3 to sqrt(n) by step of 2, if ith entry in the array is still True, set all entries from i^2 to the end of the array by step of 2*i to False (these will be the multiples of i).

最后留在数组中的所有奇数True条目都是素数.

All odd True entries that are left in the array in the end, are prime.

所有找到的数字和 2 都是 n 下面存在的所有质数.

All thus found numbers, and 2, are all the prime numbers that exist below n.

这篇关于质数发生器解释?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！