-4

こんにちは、この問題で SIGSEGV エラーが発生しました。問題がどこにあるのかわかりませ ん 。これが私のコードです。事前に感謝してください。

int main()
{
   int t;   // test cases

   cin>>t;

   while(t--)
   {
      long int m,n;
      cin>>m>>n;


      if( 1 <= m <= n <= 1000000000 && n-m<=100000)
      {
         bool a[n];
         for(long int i=2;i<=n;i++)
         {
            a[i]=true;  // set all to true
         }
         a[0]=false;
         a[1]=false;
         for( long int i=2;i*i<=n;i++)
         {
            if(a[i])
            {
               for( long int k=i*i;k<=n;k+=i)
               {
                  a[k]=false;
               }
            }
         }
         for(long int i=m;i<=n;i++)
         {
            if(a[i])
               cout<<i<<endl;         //Now all i such that a[i] is true are prime.
         }
         cout<<endl;
      }
      else
         return -1;
   }

   return 0;
}
4

3 に答える 3

2

10 9の平方根より下に 3401 個の素数があります。10 9の上限を下回る数字のセグメントをふるいにかけるために必要なのはこれだけです。

したがって、まず、2 から 31622 までのセグメントをふるいにかけます。結果の 3401 個の素数を配列に格納します。

次に、数値のペアごとにm <= n, m >= n - 100000、セグメントmをn含む一時的な配列を作成し、最初のステップで計算した素数でふるいにかけます。素数の正方形が指定された より上にある場合、各ふるい分けを停止できますn。

for( i=0; primes[i]*primes[i] <= n; ++i)
{
    ....

エラトステネスの「オフセットふるい」に関する私の投稿も参照してください。

于 2013-05-28T07:40:30.240 に答える