1

SPOJの問題PRIME1を解決するために、エラトステネスのふるいを実装しました。出力は問題ありませんが、私の提出は制限時間を超えています。どうすれば実行時間を短縮できますか？

int main()
{
  vector<int> prime_list;
  prime_list.push_back(2);
  vector<int>::iterator c;
  bool flag=true;
  unsigned int m,n;
  for(int i=3; i<=32000;i+=2)
  {
    flag=true;
    float s = sqrt(static_cast<float>(i));
    for(c=prime_list.begin();c<=prime_list.end();c++)
    {
        if(*c>s)
            break;
        if(i%(*c)==0)
        {
            flag=false;
            break;
        }
    }
    if(flag==true)
    {
        prime_list.push_back(i);
    }
  }
  int t;
  cin>>t;
  for (int times = 0; times < t; times++)
  {
    cin>> m >> n;
    if (t) cout << endl;
    if (m < 2)
        m=2;
    unsigned int j;
    vector<unsigned int> req_list;
    for(j=m;j<=n;j++)
    {
        req_list.push_back(j);
    }
    vector<unsigned int>::iterator k;
    flag=true;
    int p=0;
    for(j=m;j<=n;j++)
    {
        flag=true;
        float s = sqrt(static_cast<float>(j));
        for(c=prime_list.begin();c<=prime_list.end();c++)
        {
            if((*c)!=j)
            {
                if((*c)>s)
                    break;
                if(j%(*c)==0)
                {
                    flag=false;
                    break;
                }
            }
        }
        if(flag==false)
        {
            req_list.erase (req_list.begin()+p);
            p--;
        }
        p++;
    }
    for(k=req_list.begin();k<req_list.end();k++)
    {
        cout<<*k;
        cout<<endl;
    }
  }
}
4

7 に答える 7

4

エラトステネスのふるいアルゴリズムを実装していないため、コードが遅くなります。アルゴリズムは次のように機能します。

1) Create an array with size n-1, representing the numbers 2 to n, filling it with boolean values true (true means that the number is prime; do not forget we start counting from number 2 i.e. array[0] is the number 2)
2) Initialize array[0] = false.
3) Current_number = 2;
3) Iterate through the array by increasing the index by Current_number.
4) Search for the first number (except index 0) with true value.
5) Current_number = index + 2;
6) Continue steps 3-5 until search is finished.

このアルゴリズムには O(nloglogn) 時間がかかります。実際にはもっと時間がかかります (O(n^2))。ところで、2 番目のステップ (n と m の間の素数を検索する場所) では、それらの数が再び素数であるかどうかを確認する必要はありません。理想的には、アルゴリズムの最初のフェーズでそれらを計算します。

リンクしたサイトでわかるように、主な問題は、最大数 n が 10^9 であるため、サイズ n-1 の配列を実際に作成できないことです。この単純な方法で行うと、メモリの問題が発生します。この問題はあなたのものです:)

于 2010-10-05T22:20:06.657 に答える
3

あなたが持っているものを捨てて、ふるいの本当に単純な実装からやり直し、本当に必要な場合にのみ複雑さを追加します。考えられる出発点は次のとおりです。

#include <vector>
#include <iostream>

int main() {
    int number = 32000;
    std::vector<bool> sieve(number,false);
    sieve[0] = true;  // Not used for now, 
    sieve[1] = true;  //   but you'll probably need these later.

    for(int i = 2; i<number; i++) {
        if(!sieve[i]) {
            std::cout << "\t" << i;
            for (int temp = 2*i; temp<number; temp += i)
                sieve[temp] = true;
        }
    }
    return 0;
}

指定された範囲 (最大 32000) では、これは 1 秒未満で実行されます (出力がファイルに送信されます。画面に送信されると、通常は遅くなります)。そこから先はあなた次第ですが…

于 2010-10-05T22:19:13.260 に答える
2

エラストテネスのふるいを実装したかどうかはよくわかりません。とにかく、アルゴリズムをある程度高速化できるいくつかのことは次のとおりです。スペースを事前に割り当てることにより、ベクターコンテンツの複数の再配置を回避します（ lookup std::vector<>::reserve）。操作sqrtは高価であり、テストを変更することで完全に回避できる可能性があります (x*x > yをチェックする代わりにx < sqrt(y).

繰り返しになりますが、実際のアルゴリズムを修正することで、はるかに優れた改善が得られます。ざっと見てみると、すべての候補を反復処理し、それらの候補ごとに、因子になる可能性のあるすべての既知の素数で除算しようとしているように見えます。エラストテネスのふるいは、1 つの素数を取り、その素数のすべての倍数を 1 回のパスで破棄します。

ふるいは、数値が素数であるかどうかをテストする操作を実行しないことに注意してください。以前に破棄されていない場合、素数です。素数ではない各数は、一意の要素ごとに 1 回だけアクセスされます。一方、アルゴリズムはすべての数を何度も処理しています（既存の素数に対して）

于 2010-10-05T22:20:18.000 に答える
1

ふるいを少し高速化する1つの方法は、この行で mod 演算子を使用しないことだと思います。

if(i%(*c)==0)

（比較的）高価な mod 操作の代わりに、ふるいを追加して前方に反復した場合。

正直、これが正しいかどうかはわかりません。コメントがなく、変数名が 1 文字であると、コードが読みにくくなります。

于 2010-10-05T21:57:10.737 に答える
1

私が問題を理解している方法は、範囲 [m,n] 内のすべての素数を生成する必要があるということです。

[0,n] からすべての素数を計算する必要なくこれを行う方法は、これが速度を低下させている可能性が最も高いため、最初に範囲 [0,sqrt(n)] 内のすべての素数を生成することです。

次に、結果を使用して [m,n] の範囲でふるいにかけます。素数の最初のリストを生成するには、エラトステネスのふるいの基本バージョンを実装します (Wikipedia の記事の疑似コードからの単純な実装でうまくいきます)。

これにより、問題を短時間で解決できるはずです。

エラトステネスのふるいの簡単な実装例を次に示します。

std::vector<unsigned> sieve( unsigned n ) {
    std::vector<bool> v( limit, true ); //Will be used for testing numbers
    std::vector<unsigned> p;            //Will hold the prime numbers

    for( unsigned i = 2; i < n; ++i ) {
        if( v[i] ) {                    //Found a prime number
            p.push_back(i);             //Stuff it into our list

            for( unsigned j = i + i; j < n; j += i ) {
                v[i] = false;           //Isn't a prime/Is composite
            }
        }
    }

    return p;
}

0 から n までの素数のみを含むベクトルを返します。次に、これを使用して、前述のメソッドを実装できます。ここで、実装は提供しませんが、基本的にエラトステネスの篩と同じことを行う必要がありますが、すべての整数 [2,n] を使用する代わりに、見つけた結果を使用するだけです。これがあまりにも多くを与えているかどうかわかりませんか？

于 2010-10-05T22:36:37.943 に答える
-1

元の質問のSPOJ 問題では、エラトステネスの篩で解決する必要があるとは指定されていないため、この記事に基づく代替ソリューションを次に示します。私の 6 年前のラップトップでは、最悪の単一テスト ケース (nm=100,000) で約 15 ミリ秒で実行されました。

#include <set>
#include <iostream>

using namespace std;

int gcd(int a, int b) {
   while (true) {
      a = a % b;

      if(a == 0)
         return b;

      b = b % a;

      if(b == 0)
         return a;
   }
}

/**
 * Here is Rowland's formula. We define a(1) = 7, and for n >= 2 we set 
 *
 * a(n) = a(n-1) + gcd(n,a(n-1)). 
 *
 * Here "gcd" means the greatest common divisor. So, for example, we find
 * a(2) = a(1) + gcd(2,7) = 8. The prime generator is then a(n) - a(n-1),
 * the so-called first differences of the original sequence.
 */
void find_primes(int start, int end, set<int>* primes) {
   int an;        // a(n)
   int anm1 = 7;  // a(n-1)
   int diff;

   for (int n = start; n < end; n++) {
      an = anm1 + gcd(n, anm1);

      diff = an - anm1;

      if (diff > 1)
         primes->insert(diff);

      anm1 = an;
   }
}

int main() {
   const int end = 100000;
   const int start = 2;

   set<int> primes;

   find_primes(start, end, &primes);
   ticks = GetTickCount() - ticks;

   cout << "Found " << primes.size() << " primes:" << endl;

   set<int>::iterator iter = primes.begin();
   for (; iter != primes.end(); ++iter)
      cout << *iter << endl;
}
于 2010-10-05T23:55:39.613 に答える
-3

コードのプロファイルを作成し、ホットスポットを見つけて、それらを排除します。Windows、Linuxプロファイラーリンク。

于 2010-10-05T21:49:00.697 に答える