讲解过素数判定之后，老师又讲了一个威尔逊定理，挺有意思的，竟然是判断素数的定理，还是充分必要条件！。。然并卵，判定增长是指数级的，并没有什么实用价值。。不过还是总结一下这个学院派的定理吧。。。。也不知道猴年马月能用上，不过多知道一条定理总是好的！
定理内容：当( p -1 )! ≡ -1 ( mod p ) 时，p为素数。其逆定理也正确。定理的证明这里从略，下面主要讲一下它的应用。
根据威尔逊定理，想要判断一个数是否是素数，只需要从1到比该数小1的数统统乘起来，然后加1，得到的和如果能整除该数，则该数就是一个素数。这个判定方法虽然是判定素数的充要条件，但是并没有太多的实用价值：其判定时需要的计算量成指数级增长。例如判定41243是否是一个素数，就需要计算1*2*3*4...41241*41242.且不说乘法计算下来的时间问题了，就是想找一个空间存储计算得到的值就是一个几乎难以解决的问题。
不过关于威尔逊定理有一些推论：形如4x＋1的质数，一定可以表示为两个整数的平方和，而且表达方法是唯一的；
而形如4x－1的质数，不可能是两个整数的平方和。
-----------------------------------------
质数 4x＋1型＝a2＋b2 4x－1型
3 4×1－1
5 4×1＋1＝22＋12
7 4×2－1
11 4×3－1
13 4×3＋1＝32＋22
17 4×4＋1＝42＋12
19 4×5－1
23 4×6－1
29 4×7＋1＝52＋22
31 4×8－1
37 4×9＋1＝62＋12
41 4×10＋1＝52＋42
43 4×11－1
------------------------------------------
我们知道大于3的奇数都能写成4x+1和4x-1(其实就是4k+3) 的形式，所以，威尔逊定理的这个推论，覆盖了2以外所有的质数！这大大的增加了人们对素数的认识程度！
曝一道习题吧：威尔逊定理的应用。
HDU 2973 YAPTCHA
此题运用威尔逊定理分析之后，实际上求得是1~n之间素数的个数，由于题目中t的值较大，这里可以先将1~106之间的素数用筛法筛出来，然后直接线性时间内输出结果即可。
代码如下：
1 #include <cstdio> 2 #include <cstring> 3 4 const int MAXN = 1e6+10; 5 bool u[3*MAXN]; //若i为素数则标记为1.；之所以乘3,是为了保证筛得的数够u[3*i+7]用 6 int prime[3*MAXN], cnt = 0; //cnt记录素数个数 7 int ans[MAXN], t, n; 8 9 int main() 10 { 11 memset(u, true, sizeof(u)); 12 13 //这一步的核心是筛法求素数 14 for(int i=2; i<3*MAXN; ++i) 15 { 16 if(u[i]) prime[cnt++] = i; //用prime数组记录素数 17 for(int j=0; j<cnt && i*prime[j]<3*MAXN; ++j) 18 { 19 u[i*prime[j]] = false; //把素数prime[j]的i倍的数全部筛掉 20 if(0 == i%prime[j]) break;//符合该条件的i已经标志prime[i]=0,故无需重复标记 21 } 22 } 23 24 //这一步的核心是威尔逊定理，可以推出简单化结论 25 ans[0] = 0; 26 for(int i=1; i<MAXN; ++i) 27 { 28 ans[i] = ans[i-1] + u[3*i+7];//若3i+7为素数，则该项的值为1，就在Sn=S(n-1)+1. 29 } 30 31 scanf("%d", &t); 32 while(t--) 33 { 34 scanf("%d", &n); 35 printf("%d ", ans[n]); 36 } 37 return 0; 38 }