python之素数查找函数的优化

经过 10 分钟的工作，我编写了如下所示的函数。它返回低于参数的所有素数的列表。为了尽可能快地实现此功能，我使用了所有已知的编程和数学技巧。要找到所有小于一百万的素数，大约需要 2 秒。

您认为有进一步优化它的可能性吗？有什么想法吗？

def Primes(To): 
  if To<2: 
    return [] 
  if To<3: 
    return [2] 
  Found=[2] 
  n=3 
  LastSqr=0 
  while n<=To: 
     k=0 
     Limit=len(Found) 
     IsPrime=True 
     while k<Limit: 
         if k>=LastSqr:  
            if Found[k]>pow(n,0.5):  
               LastSqr=k 
               break 
         if n%Found[k]==0: 
            IsPrime=False 
            break 
         k+=1 
     if IsPrime: 
        Found.append(n) 
     n+=1 
  return Found 

请您参考如下方法:

您可以使用一些技巧来加快速度，使用埃拉多色的基本筛法。一种是使用 Wheel Factorization跳过计算已知不是素数的数字。例如，除了 2 和 3 之外，所有素数都与 1 或 5 mod 6 全等。这意味着您根本不必处理每 6 个数字中的 4 个。

在下一级别，所有素数都与 1、7、11、13、17、19、23 或 29 的 mod 30 全等。您可以从每 30 个数字中丢出 22 个。

这是不计算或存储偶数的 Erastothenes 筛法的简单实现:

def basic_gen_primes(n): 
    """Return a list of all primes less then or equal to n""" 
    if n < 2: 
        return [] 
 
    # The sieve.  Each entry i represents (2i + 1) 
    size = (n + 1) // 2 
    sieve = [True] * size 
 
    # 2(0) + 1 == 1 is not prime 
    sieve[0] = False 
 
    for i, value in enumerate(sieve): 
        if not value: 
            continue 
 
        p = 2*i + 1 
 
        # p is prime.  Remove all of its multiples from the sieve 
        # p^2 == (2i + 1)(2i + 1) == (4i^2 + 4i + 1) == 2(2i^2 + 2i) + 1 
        multiple = 2 * i * i + 2 * i  
        if multiple >= size: 
            break 
 
        while multiple < size: 
            sieve[multiple] = False 
            multiple += p  
 
    return [2] + [2*i+1 for i, value in enumerate(sieve) if value] 

如前所述，您也可以使用更奇特的筛子。