怎样判断一个数是素数,如何快速判断一个数是素数？

，抽时间速度答题。

如何判断一个数是素数，而且还要求快速，比如给一个数N，判断数N是否是素数，该怎么做呢？

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数，这样的数称为质数。

它的因素只有1和它本身，而在所有实数集合中，这样的素数有无数个。

那么一般的方法可以用下面的这种方法来计算，通过寻找所有的因数，但是这种方法其实当n这个数很大的时候是很慢的。那么有没有更快的方法呢？答案是必须的。

费马小定理

费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出，其内容为：假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

有这个费马小定理以后，再回去看看这个判断素数的问题，是否可以用费马小定理来解决呢？先来看一个HOJ的题目，题目链接在这儿：

http://acm.hit.edu.cn/hoj/problem/view?id=1356

题目大意就是，给你一个正整数，需要你编一个程序，去判断这个数是不是素数。

既然让你判断是不是素数，如果你用最上面的那个很原始的方法去，必然Time out，这个时候就需要用到费马小定理了，先来看看我N年轻写的代码。

下面来讲讲这个答案哈。费马小定理里面讲到，假如p是质数，且gcd(a,p)=1，那么 a^(p-1)≡1（mod p），即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。也就是说我们sample几个素数a，去验证整个p，如果满足了费马小定理，那么这个p是素数的可能性非常非常的大。具体需要sample几个，这个貌似有正面，其实3-4个基本上就满足了，非素数是很容易就被检测出来的。其实这个问题就转换为如何去快速的算次方和模运算了，恰恰有一个理论叫做蒙哥马利幂模运算，具体这个方法可以去网上自己搜一下，也就是对应我们代码里面的mod那个函数。