21319_PrimeJudge

Given a positive integer, your job is writing a program to determine whether it is a prime number or not.

There are several tests. Each test consists of a positive integer n (no more than 2³¹) on a single line. Input is terminated by end of file.

For each integer in the input, print a "YES" if it is a prime number, otherwise print a "NO" instead.

4
5
6

NO
YES
NO

题目大意就是给出一个不超过2³¹的数，来判断它是否为素数，对于此题的规模，一般的素性检测显然不行，要用到Miller rabin, 这个算法主要是基于费尔马小定理，如果n为素数，那么对于小于n的数a有a^(n-1) ≡ 1(modn)。显然这是一个必要条件，然而只要满足这个条件就基本上是一个素数了，称为'伪素数'，正确率为1-(1/4)^m，m用不同的基测试的次数，所以多测试几次就可以保证结果的正确了。而初学者在实现Miller rabin算法的时候或多或少都会遇到一些问题，这里通过此题来给出Miller rabin的一个简单的实现方法。

给定一个数n，0 < n < 2³², 判断是否是素数。

普通的筛法，不能解决问题，所以用近似的方法。

费马小定理: 如果P是一个素数，且0则a^(p-1) ≡ 1(mod p)。例如，67是一个素数，则2^66mod 67=1。 利用费马小定理，对于给定的整数n，可以设计一个素数判定算法。 通过计算d=2^(n-1)mod n来判定整数n的素性。当d不等于1时，n肯定不是素数；当d等于1时, n则很可能是素数。但也存在合数n使得2^(n-1) ≡ 1(mod n)。例如，满足此条件的最小合数是n=341。为了提高测试的准确性，我们 可以随机地选取整数1然后用条件a^(n-1) ≡ 1(mod n)来判定整数n的素性。例如对于n=341，取a=3时，有3³⁴⁰ ≡ 56(mod 341)。故可判定n不是素数。

求 a^(p-1) ≡ 1(mod p)时，用分治方法，一点点缩小规模。

其中 费马小定理毕竟只是素数判定的一个必要条件。满足费马小定理条件的整数n未必全是素数。有些合数也满 足费马小定理的条件。这些合数被称做Carmichael数，前3个Carmichael数是561,1105,1729。Carmichael数是非常少 的。在1~100000000范围内的整数中，只有255个Carmichael数。利用下面的二次探测定理可以对上面的素数判定 算法作进一步改进，以避免将Carmichael数当作素数。

二次探测定理: 如果p是一个素数，且0则方程x² ≡ 1(mod p)的解为x=1, p-1。 但是我的代码里没有用，测试数据里也没有这样的数。