-1

答えを出すのに永遠に時間がかかります。答えを処理しているように見えますか? 同様の質問を見たことがありますが、このコードの何が問題なのか教えてください。

#include<stdio.h>
main()
{
    int flag=0;
    unsigned long long int j,z,ino,i;
    scanf("%llu",&ino);
    for(i=2;i<=ino/2;i++)
    {
        flag=0; 
        if(ino%i==0)
        {
            for(j=2;j<=i/2;j++)
            {
                if(i%j==0)
                {
                    flag=1;
                }
            }

            if(flag==0)
            {
                z=i;
            }
        }
    }

printf("%llu",z);
}

問題は次のとおりです。

13195 の素因数は 5、7、13、29 です。600851475143 の最大の素因数は?

4

1 に答える 1

0

コードが間違っているということではなく、効率が悪いということです。

数値が素数かどうかをテストするコードを見てみましょう。

            for(j=2;j<=i/2;j++)
            {
                if(i%j==0)
                {
                    flag=1;
                }
            }

主に 7919 (素数) をテストする場合、ループはほぼ 4,000 回実行されます。

しかし、あなたの状態ははるかに強い可能性があります。あなたが書いた場合：

        for(j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
            {
                flag=1;
            }
        }

その後、素数テストは依然として正しいですが、実行する必要があるのは 88 回だけであり、大幅な改善です。漸近的に、素数性をテストするための線形 (n 単位) アルゴリズムからルート n 時間で実行されるアルゴリズムに変更されました。素数性をより速くテストできますが、Project Euler の少なくとも最初の 50 の問題についてはそうする必要はありません。 .

このプロジェクトのオイラー問題のコードの私のバージョンは、素数のチェックを除いて (そして Java で)、0.023631 秒で実行されます。

于 2014-04-07T21:05:11.057 に答える