1

经过 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
4

3 回答 3

5

您可以使用一些技巧来加快速度，使用基本的erastothenes 筛子。一种是使用轮因式分解来跳过计算已知不是素数的数字。例如，除了 2 和 3，所有素数都与 1 或 5 mod 6 相等。这意味着您根本不必处理每 6 个数字中的 4 个。

在下一个级别，所有质数都与 1、7、11、13、17、19、23 或 29，模 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]

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

于 2012-07-31T13:58:54.903 回答
4

您只能检查奇数。那么为什么不使用 n+=2 而不是 n+=1 呢？

于 2012-07-31T13:44:26.690 回答
2

谷歌和维基百科以获得更好的算法。如果您只是在寻找小的素数，这可能已经足够快了。但是对于大素数，真正的算法要快得多。

http://en.wikipedia.org/wiki/Quadratic_sieve

从那个页面开始。

将 n 增加 2 而不是 1。?

于 2012-07-31T13:41:09.710 回答