波波桑
根据数的不同范围和要求，我总结主要有三种常用的方法判断一个数是否是素数
一. 一般方法
直接判断在sqrt(n)范围内有没有整数能整除n，如果有则不是素数，否则就是素数。
但这种方法比较暴力，如果n过大是不行的，而且一个一个去计算太慢了，如果我要找出10000000以内的所有素数，那计算量是相当大，效率不高。
二. 基于线性筛法
如果要找出10000000以内的所有素数，那么就要使用线性筛法了。基本原理是：先把所有整数列出来，然后把2的倍数全部剔除，然后是三的，以此类推，遍历所有素数，把倍数全部划去。划去的是合数，剩下的就是素数了。
那么，如果n特别大的时候呢，比如n=10^12，又怎么判断呢？ 这时候就需要Miller-Rabin素数测试方法了。
三. Miller-Rabin素数测试
它是基于二次探测定理进行判断的，定理描述如下
代码实现比较长，截图在下面
一般情况下第二种和第三种方法用得最多。
薛定谔的小猫猫
如何判断一个数是素数，而且还要求快速，比如给一个数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那个函数。
看懂了的，记得给一个赞，听说点赞的小伙伴都走上了人生巅峰。不懂的评论区见。
波波桑
我们要判断一个数是素数，就要排除所有小于这个数的素数是该数的因数。没有“更巧妙”的方法。
然而，我们有一个规律可资利用，这样可以减少工作量：一个数N，我们可以只试验比“根号N”小的所有素因数，而不必试验所有比N小的素因数。
bratskid
一个小循环就可以了
南阳理工14软件
不知道现在世界上不用计算机，最先进判定质数的方法是什么，我自以为有较先进的方法。比如已知1万内所有质数，分解58965539是质还是合。要多长时间。
