文章目錄

这个问题对于学习编程的人来说不陌生,但并没有想象中那么简单,这里面还是很深的。一般来说是用比这个数小的素数去除,如果都不能整除,则是素数。可是这种方法必须要求你知道比这个数小的所有素数,所以我觉得不是很实用。

去年找实习时,微软的面试官也问了我这题。刚开始只想到最基础的方法,假设需要判断的是n, 如果n是2则是素数,如果n是1或者是大于2的偶数,则是素数,如果n是大于2的奇数,则从2开始到 n的平方根,如果n可以被其中任何一个整除则这个数不是素数,否则是素数。

之后面试官问还有没有更好的方法,考虑之后,想到《C语言名题百则精选中曾提到过一种方法,对于大于等于6的数,都可以表示成6n,6n + 1,6n + 2, 6n + 3, 6n + 4, 6n + 5,其中只有6n + 1和6n + 5是素数,所以对于大于6的数,如果不能被2 , 3 , 5整除,则只需用6n + 1和6n + 5这些数去除。

最近在做欧拉工程第58题,我先生成一个很大的素数表,然后来判断是否是素数,可是这个题目中用到的素数实在是太大了,这种方法不实际。之后用了前面两种方法,也是不行,速度太慢了。最后上网找方法,找到了米勒-拉宾素性测试法,终于把问题解决了。难道说,当时的面试官是想问这种方法?
以下内容来自http://en.wikipedia.org/wiki/Miller-Rabin_primality_test 。这个方法需要用到费马小定理,x^2 = 1 (mod p),费马这厮真是有趣,搞出几个定理都不给出证明,这个小定理还好,最要命的是那个大定理,耗费了几百年才被人给出证明。这里空白太少,写不下证明,只好直接拿来用了。

先给一个引理,当p是素数,若x^2 = 1 (mod p),则x = 1(mod p)或者 x = -1(mod p),这个引理的证明很简单,由x ^ 2 = 1 (mod p)得(x + 1)(x – 1) = 0 (mod p),而由于p是素数,所以x + 1 = 0 (mod p)或者x – 1 = 0 (mod p).

现在设n是一个素数且n > 2,则 n – 1一定是偶数,并且可以表示成2 ^s d的形式,其中s和d都为正整数,且d是奇数。那么对于任意2 <= a < n,
a^d = 1 (mod n)或者a^(2^r
d) = - 1(mod n),其中0 <= r <= s – 1。

证明如下:
由费马小定理可知,当n是素数时
a^(n – 1) = 1 (mod n), 我们将n – 1表示成2^s d,再由上面的引理得,如果我们对n – 1进行开方,则可以得到a^(2^(s – 1) d)=1 (mod n)或者a^(2^(s-1) *d) = -1 (mod n),如果是后者,则已经满足了,如果是前者,则继续这个开方过程,如果我们一直都是得到1,最终就是
a^d = 1(mod n).

而米勒-拉宾测试法就是用了这个定理的逆否命题。也就是,如果 a^d != 1 (mod n)且a^(2^r *d) != -1 (mod n)对于所有的0<=r<=s-1,则n不是素数。

文章目錄