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;
}
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。