素数就是除了1和他本身 没有别的数能够把他整除
对于给定整数n
最暴力的方法就是枚举从2到n的所有数
但是这样效率肯定很慢
素数表
思维很简单 对于一个素数 他的整数倍一定不是素数 所以我们建立一个素数表 对于给定数n 先检测能不能被素数表整除 如果不能再进行枚举
但其实这种方式很无聊 也快不了多少
快速素数检验
如果我们要检验n是不是一个素数
我们不如检验他是不是一个合数
合数就是不是素数的数
且对于任意合数n 一定存在以下三种情况之一
1：
$$ n=x* y (x,y=\sqrt{a}) $$
2:
$$ n = x*y (x<\sqrt{a},y>\sqrt{a}) $$
3:
$$ n=x*y(x>\sqrt{a},y<\sqrt{a}) $$
这代表 任意一个合数n 必有一个小于根号n的数是n的因数（也就是n可以被他整除）
那么对于任意数x 只需要检测从2到根号x的数能否被整除即可
更快的方法？
当然有 虽然上面的方法很多情况已经够用了
下面是费马小定理：
如果n是一个合数 那么一定有一个不能被n整除的数a 满足下列关系：
$$ a^{n-1} (mod) N =1 $$
但是如果不满足这个关系 他也不一定是个素数
我们可以对被费马小定理筛下来的数进行上面的快速素数检验 但是也快不了多少
再快就要超出我的理解范围了
下面给出链接