素数（也叫质数）是个神奇的东西，它的定义是“如果一个数只有 1 和它本身两个约数，那么它就是一个素数”。而在各种程序算法中，也经常会出现素数的身影。那么我们来讨论一下常用的那些素数生成的小算法。
素数的神奇之处在于它看起来像是有某种规律，但仔细研究之下却又找不出它的出现规律。所以判断一个数是不是素数，是没有准确判定公式可用的，也因此，素数的判断发展出了两个方向：确定性素数检测与概率性素数检测。
为何要如此麻烦？
检测个素数为何要如此麻烦？原因是素数的无规则出现导致的检测困难，不同的算法在时间上有明显的差异，并且这个差异随着要检测的数增大而成倍的增大。
概率性素数检测
由于本文仅仅是个入门级代码试验，而且我们要的是确定性素数，所以这里仅仅做个科普：
确定性素数检测是如此之难，以至于人们的目光转向了这种不太靠谱的概率性算法。其中比较常用的是“米勒-拉宾素性检验法”。它的理论基础是由费马素数判定法延伸而来的，用通俗的话来说，它是这样进行的（米勒测试具体方法在这里）：
针对一个数 N，想要判断它是否是一个素数，就对它进行米勒测试，如果它未能通过测试，那这个数一定是合数。而如果它通过了第一次米勒测试，那么它有 3/4 的机率是一个素数。这样，当你对它进行足够多次的米勒测试后，它如果仍然能够通过，那它不是素数的机率只有 (1/4)^k，其中 k 是进行了多少次独立的米勒测试。这样的数叫做卡迈克尔数。由于测试的次数可以尽可能的多，那么最终得到“伪素数”的机率实际上是可控的。
确定性素数检测
试除法：可以暴力但不能无脑
虽然米勒测试能够以很小的时间复杂度来筛出素数，可毕竟它是一个概率性算法。当你需要一个百分之百的确定性素数时，那就要多花点时间了。最经典的确定性素数检测法是“试除法”，也就是暴力的去穷举所有的可能。但暴力运算可也不是那么的无脑，先来看这张图：
我使用了下面的代码来计算某个范围内素数的个数，在素数判断时使用了“试除法”。但在试除的上限上做了区分，有 i < N， i <= N / 2，i <= sqrt(N)。可以看到，在数据规模增大的时候，四种方法的时间还是有很大区别的。即使是使用了4线程来并行计算，仍然速度很慢。
那么我们来讨论一下为何可以只判断到 N/2 甚至 sqrt(N)？由于素数的判断实际上就是找约数，如果它有一个约数 2 ——这是除了 1 以外可能的最小的约数了，那么另一个数一定是 N/2，因此我们可以只遍历到 N/ 2。从这个方向上延伸，如果它的其中一个约数是 3，是 4，...，另一个数就会越来越“小”。由于 sqrt(N) ^ 2 == N。 也就是说：当两个数的乘积等于 N 时，那么这两个数通常是分布在 sqrt(N) 的两边，一个大一个小。而最极端的情况就是它们两个数都是 sqrt(N). 那如果找遍了小于等于 sqrt(N) 的数都没有 N 的约数的话，可以断定在剩下的部分，你是无法找到两个大于 sqrt(N) 的数作为它的约数的。从另一个方向思考：如果 a, b 都大于 sqrt(N)，很显然， a * b 必然是大于 N 的。
筛法：范围确定性素数生成的终极杀手
筛法是一个巧妙的，计算一个数值范围内确定性素数的好办法，它的基本思想是这样的：有一个大的数组 data[]，数组每个位置的下标代表对应的数字，此下标对应的值代表此数字是否为素数。先假设所有的数都是素数，然后开始遍历，当找到第一个素数 i 时，我们就可以知道，i * 2，i * 3，...都是合数，也就是把数组内剩下 i 的倍数的数标记为合数。只需对数组做一次这样的遍历，还没有被标记的，就是筛选出来的素数。下面是一段使用筛法的测试代码：
对比上面的试除法，这个方法求 10000000 以内的所有素数只需要 secs: 1, nanos: 281009418。
在没有特别指明时以