素数判断的那些事儿

素数判断的那些事儿

来源: | 浏览: 784 | 评论: 0 发表时间: 2016-05-22 17:00:14

素数(也叫质数)是个神奇的东西,它的定义是“如果一个数只有 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。




相关文章
没有人评论过此文,还不快抢个沙发
  • 昵称: *
  • 邮箱:
  • 网址:
  • 记住我的信息
  • Color
  • Red
  • Blue
  • Code
  • bash
  • cpp
  • css
  • java
  • js
  • perl
  • php
  • python
  • ruby
  • sql
  • xml








最新评论