3

プロジェクト オイラーの問題を解いていて、現在 10 位です。

まず第一に、私は他の解決策があることを知っています.現在、エラトステネスのふるいを使用して別の方法を書いています. このコードが機能しない理由を理解するために、あなたの助けが必要です。

これは私のコードです (問題は、200 万未満のすべての素数の合計を見つけることです)。素数チェック方法は問題なく機能しているように見えますが、結果は本来あるべきものよりもはるかに劣っています。

class Euler10
{
    public static void Main()
    {
        long sum = 0; // Was originally an int. Thanks Soner Gönül!
        for(int i = 1; i < 2000000; i++) 
        {
            if (CheckIfPrime(i) == true)
                sum += i;
        }
        System.Console.WriteLine(sum);
        System.Console.Read();
    }

    static bool CheckIfPrime(int number)
    {
        if (number <= 1)
            return false;
        if (number == 2)
            return true;
        if (number % 2 == 0)
            return false;

        for (int i = 3; i*i < number; i += 2)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }
}

取得した数値は 1,308,111,344 で、本来あるべき数値よりも 2 桁低くなります。コードはとても単純なので、このエラーに困惑しています。

編集：合計を長くすると、数字の問題が解決しました。みんなありがとう！しかし今、私は答えとして 143042032112 を得ます: CheckIfPrime() の i*i は常に正しいとは限りません。sqrt() 関数を使用して (int キャストを補うために) 1 つ追加すると、正しい結果が得られます。正しい CheckIfPrime() 関数は次のとおりです。

 bool CheckIfPrime(int number)
    {
        if (number <= 1)
            return false;
        if (number == 2)
            return true;
        if (number % 2 == 0)
            return false;
        int max = 1 + (int)System.Math.Sqrt(number);
        for (int i = 3; i < max; i += 2)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }

編集 2: Ness は、コードをさらに最適化するのに役立ちました (数値の平方根を計算して i と比較するのは、i^2 を上げてから数値と比較するよりも遅くなります): 元の方法の問題は、それが取り込まれなかったことですnumber が i の正確な 2 乗であるエッジ ケースを考慮して、false ではなく true を返すことがあります。したがって、CheckIfPrime() の正しいコードは次のとおりです。

bool CheckIfPrime(int number)
    {
        if (number <= 1)
            return false;
        if (number == 2)
            return true;
        if (number % 2 == 0)
            return false;

        for (int i = 3; i*i <= number; i += 2)
        {
            if ((number % i) == 0)
                return false;
        }
        return true;
    }

人々に再び感謝します！

4

5 に答える 5

3

int32 ビット変数の最大値を超える数値を保持するために32 ビットを使用しようとするため、コードは機能しません。問題の答えは142,913,828,922で、38 ビットが必要です。

のデータ型を に変更すると、この問題が解決sumするはずです。long

于 2013-05-28T10:25:15.080 に答える
2

intforsum変数 which isを使用していますが、 which is32-bitよりも多く割り当てようとしています。Int32.Maximum2,147,483,647

しかし、あなたの結果は、それを保存する143,042,032,112よりも多くのビットを必要とするものです。32

ビットlongを格納するタイプを設定します。64

long sum = 0;

ここに作業がありDEMOます。

于 2013-05-28T10:27:29.307 に答える
2

long を使用すると役立つはずです。http://msdn.microsoft.com/en-us/library/ctetwysk.aspx intが32ビットのみである64ビット整数を提供します。

于 2013-05-28T10:27:32.197 に答える
1

あなたのアルゴリズムはエラトステネスのふるいではありません。モジュロ演算子はそれを与えます。あなたのアルゴリズムは、奇数による試行分割です。エラトステネスのふるいを使用した関数は次のとおりです。

function sumPrimes(n)
    sum := 0
    sieve := makeArray(2..n, True)
    for p from 2 to n step 1
        if sieve[p]
            sum := sum + p
            for i from p * p to n step p
                sieve[i] := False
    return sum

呼び出すsumPrimes(2000000)ことで答えが得られますが、Project Euler への敬意から書き留めることはしません。この関数は O( n log log n ) の時間で実行されます。これは、元のプログラムの O( n ^2)よりもはるかに優れています。ふるい分けにはもっと良い方法がありますが、それは簡単で、簡単に正しく行うことができ、あなたの目的を含め、ほとんどの目的には十分です. 1 秒以内に回答が得られるはずです。

適切なデータ型を使用して C# に変換することは、あなたに任せます。

この問題のやや大きなバージョンに興味がある場合は、私のブログで最初の 10 億個の素数の合計を計算しました: 11138479445180240497.

于 2013-05-28T13:10:20.777 に答える