质数的正确找法

大家都知道，质数的一个臭名昭著的性质就是难找。用手找质数找到100,000能花上你一天的时间，因此只有你用一些更加系统的方法去找，才不会让你在众人面前显得过于滑稽，从而闻名全校。

那么你可能就会问了：所以怎么找质数最快？当然，在这一方面，我们就要请出我们的一个朋友——计算机——来为我们找。

你需要知道什么？

首先需要知道的，有以下四件事。

1. 在计算机算法中，常数的四则运算、位运算时间忽略不计。
2. 在计算机算法中，考虑一个算法的快慢，只考虑幂指数、对数(log, ln)等超越四则运算复杂度的部分。（如：n^2，logn，n!等）
3. 计算机的常数计算速度在任何情况下高于普通高中生。
4. 计算机没有人类智能，在未定义的情况下，它只会运算，不会解题。

Part 1：最基本的找法

最基本的找法很简单：如果正整数n不能被小于n的任何正整数整除，那么n是质数。

在这一方面不再多说，因为这个原理小学2年级就可以证明。寻找n以内所有质数的的Python代码如下：

def primes(n):
    if n < 2: return []
    r.append(2)
    p = 3
    while p <= n:
        if 0 not in [p % i for i in range(2,p)]: r.append(p)
        p += 1
    return r

这段代码的时间复杂度（不是用眼睛看出来的那个复杂度）非常大，但也很容易改进。

首先，对于大于p/2的数q，一定有q不整除p，因为q<p<2q。所以检验p是否为质数时，大于p/2的数大可不必考虑。

其次，对于大于p算术平方根的整数q，若q整除p，p/q为整数，而又因为q为整数，p/q整除p，而p/q < q，因此这样的q不必考虑，因为在前面的过程中已经排除了这样的p。

另外，对于合数q，亦不用考虑。因为q必为两个以上小于q的质数之积。

因此，其实只要考虑小于p算术平方根的质数，速度可大大增加。

Part 2：埃拉托色尼筛

埃拉托色尼筛，即列一个数列2至n，每次将第一个数作为质数取出，并去掉它的所有倍数，直到第一个数大于n的算术平方根，则余下所有数均为质数。这种算法是第一种算法的升级版，但比前者快一两个数量级。

从执行角度来解释这种现象：我们不难发现其工作原理相同。但是相较于前者，筛法省去了大量判断大小的过程，因此速度大幅提升。

def primes(n):
    if n < 2: return []
    g = [i for i in range(2,n+1)]
    r = []
    while g[0]*g[0] <= n:
        r.append(g.pop(0))
        g = [i for i in g if i % r[-1] != 0]
    return r.extend(g)

埃拉托色尼筛法在拥有高效率的同时也有很多缺点。如：

• 无法无限找质数。（否则筛2就可以筛死）
• n越大，筛的负担越大。（每次要筛的数越来越多）
• 容易内存过大。（内存利用率在大数字时甚至不到10%）

Part 3：辛达拉姆的查表法

在筛法被提出的很久、很久以后，一位叫做辛达拉姆的数学家提出了这样的方法。

你没看错，每行每列都只是等差数列而已。但是，在表中每一个数乘2加1竟然都是合数，而不在表中的每一个正整数乘2加1都是质数。关于它的证明不再赘述（对第m行第n列的数乘2加1因式分解为(2m+1)(2n+1)）。这张表的本质是所有奇数之积。

因此考虑第n行，若(n-1)/2-n无法被(2n+1)整除，则为质数。

这里直接扔出它的JavaScript：

function primes(n) {
  let g = []
  if (n>=2) g.push(2)
  for (let id = 1; id*2 < n; id ++) g.push(id*2 + 1)
  const isp = function(a) {
    if (a===2) return true
    c = (a - 1) >> 1
    for (let i = 1; i*i <= c/2; i ++) {
      if ((c-i)%(2*i+1) === 0) return false
    }
    return true
  }
  return g.filter(function(item){return isp(item)})
}

大家可以扔进谷歌浏览器试试哦！

我的分享到这里，谢谢朋友们！（有问题的话请赐教，会更新）