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;
}