2

この[質問]:http://www.spoj.pl/problems/PRIME1/のセグメント化されたふるいアルゴリズムを次のように実装しようとしました:

#include <iostream>
#include <string>
#include <set>
#include<math.h>
#include<vector>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cstdio>
#define MAX 32000 // sqrt of the upper range
using namespace std;
int base[MAX];  // 0 indicates prime

vector<int> pv;   // vector of primes

int mod (int a, int b)
{
   if(b < 0)
     return mod(-a, -b);   
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}
void sieve(){

     for(int i = 2 ; i * i < MAX ; i++ )
        if(!base[i])
           for(int j = i * i ; j <  MAX ; j += i )
                 base[j] = 1;

     for(int i = 2 ; i < MAX ; i++ )
         if(!base[i]) pv.push_back(i);

}
int fd_p(int p ,int a ,int b){  // find the first number in the range [a,b] which is divisible by prime p

/*  while(1){

        if(a % p == 0 && a !=p) break;
    a++;
    }
    return a;
*/  

    if(a != p){
        return (a + mod(-a,p)) ;

    }
    else{
     return (a + p);
    }

}
void seg_sieve(int a , int b){

    if(b < 2 ){ 
        cout << "" ;
    return;
    }
    if(a < 2){
      a = 2; 
    }
    int i,j;
    int seg_size  = b - a + 1;
    int*is_prime = new int[seg_size];
    memset(is_prime,0,seg_size*sizeof(int));

    vector<int> :: iterator p ;


    for(p = pv.begin(); p!=pv.end(); p++){
       int x = fd_p(*p,a,b);  

       for(i = x; i <= b; i += *p )
           is_prime[i - a] = 1;
      }

for(i=0; i < b - a + 1; i++)
    if(!is_prime[i])
        printf("%u\n", i + a);

 delete []is_prime ;
}


int main()
{
     sieve();
     int a,b,T;
     scanf("%d",&T);

     while(T--){
     scanf("%d%d",&a,&b);
     seg_sieve(a,b);
     printf("\n");   
     }
//     cout<<endl;
//     system("PAUSE");
     return 0;
}

それにもかかわらず、私はTLEを取得しています..他にどのような最適化が必要になるかわかりません。助けてください..

編集1：一定時間でfd_p（）を実装しようとしました... [失敗] ..このバグで私を助けることができれば..

編集 2: 問題が解決しました。

4

4 に答える 4

1

一定時間でpで割り切れる区間[a、b]の最初の数を取得できます。それをやってみてください、そして私はあなたが行ってもいいはずだと思います。

于 2012-08-17T11:36:54.413 に答える
0

改善の最後のステップを 1 つ残しました。オッズのみで作業します。

が素数であることはわかっ2ていますし、(2 以外の) 偶数は決して素数ではないこともわかっています。したがって、それらをチェックする必要はありません。

奇素数に対するエラトステネスのふるいはP = {3,5, ...} \ U {{ p 2 , p 2 + 2p , ...} | p in P }。それを実装するだけで、次のことをやり遂げることができます。

  • 2別のケースとして、特別に扱います。通常のサイズの半分の配列で作業します。ここで、オフセットの配列エントリはi奇数を表し、は最小の奇数ao + 2*iであり、 を下回っていません。つまり、2pの増分値は、配列内のオフセットのpの増分に対応します。ao = a|1a
  • オフセットふるい配列内の素数の開始奇数倍数はpと等しいかそれ以上p*pでありm = p*p >= ao ? p*p : ((ao+p-1)/p)*p; m = m&1 ? m : m+p;、 であると仮定しp <= sqrt_bます。sieve 配列の対応するオフセットは です(m-ao)/2。

補足として、あなたの命名は紛らわしいです:is_prime実際にはis_compositeです。

于 2012-08-18T17:58:56.773 に答える
0

間違っているのは、fd_p 関数が遅すぎることです。a は 10 億の範囲にある可能性があるため、ふるいを開始するのに適切な値が見つかるまで a をインクリメントすると、間違いなくタイムアウトになります。

しかし、あなたは正しい考えを持っています。

このブログ記事を参照して、動作するコードの説明を理解しやすくしてください。

http://www.swageroo.com/wordpress/spoj-problem-2-prime-generator-prime1/

于 2012-09-11T19:07:05.420 に答える
0

私は何年も前にこの問題を解決しました。nm <= 100000 1 と sqrt(1000000000) < 40000 の間のすべての素数を計算する必要があると仮定します。 n と m の間の各数値を手動でテストするよりも。これで十分だろう

 program prime1;
  Var
   t:longint;
   m,n:longint;
   i,j,k:longint;
   prime:array of longint;
   bool:boolean;
begin
 SetLength(prime,1);
 prime[0]:=2;
 for i:=3 to 40000
  do begin
   j:=0; bool:=true;
   while (prime[j]*prime[j]<= i ) do begin
     if (i mod prime[j] = 0) then begin
      bool:=false;
      break;
     end;
     inc(j);
   end;
   if (bool) then begin
    SetLength(prime,length(prime)+1);
    prime[length(prime)-1]:=i;
   end;
 end;
 readln(t);
 for k:=1 to t do begin
  readln(m,n);
  for i:=m to n do begin
   if (i=1) then continue;
   j:=0; bool:=true;
   while (prime[j]*prime[j]<= i ) do begin
     if (i mod prime[j] = 0) then begin
      bool:=false;
      break;
     end;
     inc(j);
   end;
   if (bool) then
     writeln(i);
  end;
  writeln;
 end;
end.
于 2012-08-17T13:07:27.993 に答える