2

コードは次のlimit = 8とおりです。

#include <stdio.h>
#include <math.h> // pow(x, exp)

//----------------------------------------------------------

char isMersenneLucasLehmer(unsigned int prime)
{
    unsigned 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()
{
    unsigned int limit = 8;
    findMersenneLucasLehmer(limit);
    return 0;
}

出力：

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

5代わりに最初のものを返すだけで8、理由がわかりません。

アップデート：

13以降のすべてのインデックスをスキップしています。の最後の行のどこかにエラーがあると思われますisMersenneLucasLehmer(unsigned int)。ずっと探しすぎて見つからなかった。

4

4 に答える 4

2

問題は次の行にあります。

termN = (termN * termN - 2) % mersenne;

termN(環境では 32 ビット)として宣言しましたunsigned intが、その製品はこの型で表現できないほど大きくなり、結果として生じるオーバーフローによりループが発散する可能性があります。

unsigned long long int解決策は、 (64 ビット)のようなより大きな範囲の型を使用することです。

Ideone.comの例を参照してください。

于 2016-09-07T23:35:59.963 に答える