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;

}