1.素数
(1)朴素素数测试：
对于一个数n，n要么是素数要么有一个小于等于\(\sqrt{x}\)的约数
那么\(O(\sqrt{x})\)暴力判断即可
但是n很大怎么办呢
(2)米勒拉宾素数判定:
首先要知道费马小定理
若p为质数，那么\(a^(p-1)\equiv1(mod p)\)(0<a<p)
证明：假设\(x=y\)那么对于(0<a<p),都有\(x*a\not=y*a(mod p)\)
对于一个数n，n要么是素数要么有一个小于等于\(\sqrt{x}\)的约数
那么\(O(\sqrt{x})\)暴力判断即可
但是n很大怎么办呢
首先要知道费马小定理
若p为质数，那么\(a^(p-1)\equiv1(mod p)\)(0<a<p)
证明：假设\(x=y\)那么对于(0<a<p),都有\(x*a\not=y*a(mod p)\)
原文：https://www.cnblogs.com/sssy/p/8215120.html