高速的素数算法(LogN的复杂度哦)-1

快速的素数算法(LogN的复杂度哦)---------1

如果要写一个素数算法，我想大家第一反应会是如下的代码：

(2)，Euler定理
                设X是一个自然数，并且a是一个与其互素的数，则有

(3)，Lagrange子群定理
               如果群A是B的子群，则|A|  |  |B|（A的势整除B的势，可以简单地理解为A的元素个数整除B的元素个数）

先给出这三个要用到的东西，下一节中将给出相关的证明。