质数

质数无穷多个；

素性检验：

1、埃拉托色尼筛选法

　　划掉数（2——sqart(n)）的倍数

　　复杂度：O(nlog(log(n)))

2、费马素性检验法：

　　PS：费马大定理：x^n+y^n=z^n,在n>=3时，没有整数解；　　

　　费马小定理：若p为素数，对所有的整数a, a^p-a是p的倍数，即a^p-a ≡ 0 mod p;反之，不成立；

　　费马证人数：p为合数，有a^p-a ≡ 0 mod p 不成立；

　　费马骗子数：p为合数，有a^p-a ≡ 0 mod p成立；

　　对于合数来讲，证人数占1/2;

　　算法：

　　1）整数ai属于[1,p-1], i=1,2,3,...,k

　　2) a^p-a除p余0？

　　3）不是----->证人，p为合数；

　　4）都是----->p为质数

　　　　　　　　p为合数，k个骗子，被欺骗概率为（1/2)^k

　　代码：关于快速幂以后的数字太大，会溢出上限，用大整数的话，感觉太浪费资源了，还不一定快！