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

去年找实习时，微软的面试官也问了我这题。刚开始只想到最基础的方法，假设需要判断的是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不是素数。