#include <stdio.h>
char isMersenneLucasLehmer( unsigned long int prime)
{
unsigned long long int i, termN = 4 ;
unsigned long mersenne;
unsigned int limit;
int res;
mersenne
= ( unsigned long ) pow ( 2 , ( double ) prime
) - 1 ; if ( prime % 2 == 0 )
{
return prime == 2 ;
}
else
{
res
= ( int ) sqrt ( ( double ) prime
) ; for ( i = 3 ; i <= res; i += 2 )
{
if ( prime % i == 0 )
{
return 0 ;
}
}
limit = prime - 2 ;
for ( i = 1 ; i <= limit; ++ i)
{
termN = ( termN * termN - 2 ) % mersenne;
}
}
return termN == 0 ;
}
//----------------------------------------------------------
/*
Function: findMersenneLucasLehmer()
*/
void findMersenneLucasLehmer( unsigned int limit)
{
unsigned int i, current = 0 ;
unsigned long mersenne, bitsInLong = 64 ;
for ( i = 2 ; i <= bitsInLong; i++ )
{
if ( current >= limit)
{
break ;
}
if ( isMersenneLucasLehmer( i) )
{
mersenne
= ( unsigned long ) pow ( 2 , ( double ) i
) - 1 ; printf ( "current = %lu, mersenne = %lu, index = %u\n " , current
, mersenne
, i
) ; ++ current;
}
}
}
int main( void ) {
printf ( "Size of unsigned long: %d\n " , sizeof ( unsigned long ) ) ; printf ( "Size of unsigned long long: %d\n \n " , sizeof ( unsigned long long ) ) ; findMersenneLucasLehmer( 8 ) ;
return 0 ;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgpjaGFyIGlzTWVyc2VubmVMdWNhc0xlaG1lcih1bnNpZ25lZCBsb25nIGludCBwcmltZSkKewogICAgdW5zaWduZWQgbG9uZyBsb25nIGludCBpLCB0ZXJtTiA9IDQ7CiAgICB1bnNpZ25lZCBsb25nIG1lcnNlbm5lOwogICAgdW5zaWduZWQgaW50IGxpbWl0OwogICAgaW50IHJlczsKCiAgICBtZXJzZW5uZSA9ICh1bnNpZ25lZCBsb25nKSBwb3coMiwgKGRvdWJsZSlwcmltZSkgLSAxOwogICAgaWYgKHByaW1lICUgMiA9PSAwKQogICAgewogICAgICAgIHJldHVybiBwcmltZSA9PSAyOwogICAgfQogICAgZWxzZSAKICAgIHsKICAgICAgICByZXMgPSAoaW50KXNxcnQoKGRvdWJsZSkgcHJpbWUpOwogICAgICAgIGZvciAoaSA9IDM7IGkgPD0gcmVzOyBpICs9IDIpCiAgICAgICAgewogICAgICAgICAgICBpZiAocHJpbWUgJSBpID09IDApCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJldHVybiAwOyAgCiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIGxpbWl0ID0gcHJpbWUgLSAyOwogICAgICAgIGZvciAoaSA9IDE7IGkgPD0gbGltaXQ7ICsraSkKICAgICAgICB7CiAgICAgICAgICAgIHRlcm1OID0gKHRlcm1OICogdGVybU4gLSAyKSAlIG1lcnNlbm5lOwoKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gdGVybU4gPT0gMDsKfQovLy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KCi8qCiAgICBGdW5jdGlvbjogZmluZE1lcnNlbm5lTHVjYXNMZWhtZXIoKQoKKi8Kdm9pZCBmaW5kTWVyc2VubmVMdWNhc0xlaG1lcih1bnNpZ25lZCBpbnQgbGltaXQpCnsKICAgIHVuc2lnbmVkIGludCBpLCBjdXJyZW50ID0gMDsKICAgIHVuc2lnbmVkIGxvbmcgbWVyc2VubmUsIGJpdHNJbkxvbmcgPSA2NDsKCiAgICBmb3IgKGkgPSAyOyBpIDw9IGJpdHNJbkxvbmc7IGkrKykKICAgIHsKICAgICAgICBpZiAoY3VycmVudCA+PSBsaW1pdCkKICAgICAgICB7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KCiAgICAgICAgICAgIAogICAgICAgIGlmIChpc01lcnNlbm5lTHVjYXNMZWhtZXIoaSkpICAgCiAgICAgICAgewogICAgICAgICAgICBtZXJzZW5uZSA9ICh1bnNpZ25lZCBsb25nKSBwb3coMiwgKGRvdWJsZSlpKSAtIDE7CiAgICAgICAgICAgIHByaW50ZigiY3VycmVudCA9ICVsdSwgbWVyc2VubmUgPSAlbHUsIGluZGV4ID0gJXVcbiIsIGN1cnJlbnQsIG1lcnNlbm5lLCBpKTsKICAgICAgICAgICAgKytjdXJyZW50OwogICAgICAgIH0gCiAgICB9Cn0KCmludCBtYWluKHZvaWQpIHsKCXByaW50ZigiU2l6ZSBvZiB1bnNpZ25lZCBsb25nOiAlZFxuIiwgc2l6ZW9mICh1bnNpZ25lZCBsb25nKSk7CglwcmludGYoIlNpemUgb2YgdW5zaWduZWQgbG9uZyBsb25nOiAlZFxuXG4iLCBzaXplb2YgKHVuc2lnbmVkIGxvbmcgbG9uZykpOwoJZmluZE1lcnNlbm5lTHVjYXNMZWhtZXIoOCk7CglyZXR1cm4gMDsKfQo=
stdout
Size of unsigned long: 4
Size of unsigned long long: 8
current = 0, mersenne = 3, index = 2
current = 1, mersenne = 7, index = 3
current = 2, mersenne = 31, index = 5
current = 3, mersenne = 127, index = 7
current = 4, mersenne = 8191, index = 13
current = 5, mersenne = 131071, index = 17
current = 6, mersenne = 524287, index = 19
current = 7, mersenne = 2147483647, index = 31