3

さて、まず最初に。はい、この質問はプログラミング コンテストからのものです。いいえ、コンテストは 4 時間前に終了しているので、ごまかすつもりはありません。私のコードは正しいと確信していますが、コンテストのコンパイラは間違った答えを出していると言っていました。他のコンパイラを試してみたところ、「Time Limit Exceeded」と表示されました。

では、まず、コードが正しいかどうか教えていただけますか? [あるコンパイラはそうではないと言いました]

はいの場合、どうすれば時間をより効率的にすることができますか? [別の編集者は制限時間を超えていると言った]

問題 数が 1 より大きく、1 とそれ自体以外に約数がない場合、その数は素数と呼ばれます。最初の数個の素数は、2、3、5、7、11、13 などです。整数 X が与えられたとき、X より小さくない最小の素数を見つけます

入力: 最初の行には、テスト ケース T の数が含まれます。T ケースが続きます。各テスト ケースは、別の行の整数 X で構成されます。

出力: X 以上の最小の素数を含むケースごとに 1 つの T 行を出力します。

制約: 1 <= T <= 10 1 <= X <= 1,000,000

サンプル入力: 4 8 47 90 1130

サンプル出力: 11 47 97 1151

これが私の解決策です：

int main() 
{
    int n;
    long int x, i, a;
    bool isPrime; // This flag will test if number is prime or not?
    cin>>n; // Here "n" will represent the number of test cases
    while(n)
    {
        cin>>x; // "x" is the number to be tested for the nth case

        if(x<=2)
        {
            cout<<2<<endl; // All numbers smaller than 3 will have the smallest prime number as 2.
            continue;
        }
        for(i=x;i<=1000000;i++) // Should I have checked values of "i" for odd numbers only? I forgot to try that... Would it have helped in reducing time complexity?
        {
            isPrime=true;
            for(a=2; a<i; a++) // Okay I tried making it (i/2)+1 but then the compiler said that it was a wrong answer. I am skeptical though...
            {
                if(i%a==0 and i!=2)
                    isPrime=false;
            }
            if(isPrime==true)
            {
                cout<<i<<endl;
                break;
            }
        }

        n--;
    }
    return 0;
}
4

4 に答える 4

4

混乱を避けるために、数値が素数かどうかをチェックする関数を作成します。

bool IsPrime(int x)
{
    isPrime=true;
    for(int a = 2; a < x; a++)
    {
        if (x % a == 0 && a != 2)
            return false;
    }
    return true;
}

ここでは、コードを変更せず、再構築しただけです。これは良いことです。なぜなら、この関数は小さく、改良も容易だからです。

エッジケースを削除

この関数を 2 に対して呼び出すことはないため、チェックする必要はありませa == 2ん。これにより、内側のループが小さくなり、パフォーマンスが向上します。

bool IsPrime(int x)
{
    isPrime=true;
    for(int a = 2; a < x; a++)
    {
        if (x % a == 0)
            return false;
    }
    return true;
}

少ない除数をチェック

までの約数をチェックするだけで十分であることは、よく知られた事実であり、簡単にチェックできsqrt(x)ます。これにより、パフォーマンスが大幅に向上します。

bool IsPrime(int x)
{
    isPrime=true;
    for(int a = 2; a * a <= x; a++)
    {
        if (x % a == 0)
            return false;
    }
    return true;
}

この時点で、あなたのプログラムはタイムチェッカーに受け入れられるでしょう。パフォーマンスをさらに向上させたい場合は、除数をさらに制約することができます。

素因数のみをチェック

素数ではありませんが、チェックを少なくとも奇数に制限することをお勧めします。

bool IsPrime(int x)
{
    isPrime=true;
    static const int a_few_primes[] = {2, 3, 5, 7, 11, 13};
    for (int a: a_few_primes)
    {
        if (x % a == 0)
            return false;
    }
    for(int a = 17; a * a <= x; a += 2)
    {
        if (x % a == 0)
            return false;
    }
    return true;
}

他の回答者が推奨するエラトステネスのふるいに関するメモ: それは良いことですが、テスト ケースの数が非常に少ない (10) ことを考えると、実際には必要ないかもしれません。

編集：パフォーマンスのいくつかの欠陥のある分析を削除しました。

ふるい法では、素数のリストを作成するために少なくとも 1000000 回の反復が必要です。

試行方法では、素数が見つかるまで114未満の数を試行し、10 回実行するため、反復回数は 500*114*10=570000 未満です。

于 2013-10-03T13:48:09.343 に答える
2

私はあなたのためにそれを解決するつもりはありませんが、いくつかのヒントを提供します。

  1. エラトステネスのふるいを使用すると、後で数値が素数であるかどうかを知るために使用できる配列を作成できますO(1)。
  2. 数値を読み取る前に一度 Sieve 配列を構築すると、数値を読み取ってそれぞれを一定の時間で確認できます。各数値に対して同じ計算を実行するのはやり過ぎです。
于 2013-10-03T13:27:50.323 に答える