Lucas-Lehmer算法 用来判定梅森素数
Lucas−Lehmer 算法只能用来判定梅森素数,即可以表示为 Mn = 2n − 1 的素数。
Lucas−Lehmer 序列定义如下:
其前五项的值为:
Term 0: 4,
Term 1: 4*4 – 2 = 14,
Term 2: 14*14 – 2 = 194,
Term 3: 194*194 – 2 = 37634,
Term 4: 37634*37634 – 2 = 1416317954, …
使用 Lucas−Lehmer 序列给定一整数 n 判定 x = 2n − 1 是否是梅森素数的步骤如下:
(1)根据公式
计算出第 n – 1 项的值;
(2)如果该值为 0,则x是梅森素数,否则不为梅森素数。
代码如下:
bool isPrime(int p) { long long checkNumber = pow(2, p) - 1; long long nextval = 4 % checkNumber; for (int i = 1; i < p - 1; i++) nextval = (nextval * nextval - 2) % checkNumber; return nextval == 0; }