0

spoj.pl n codechef.com に「プライム ジェネレーター」という問題があります。私はそれをうまく解決しましたが、何度も試しても送信されません。助けてください。正しいと思っていても、間違った答えが返ってきます。私が知っているすべてのケースを満たしています。問題の説明は次のとおりです ( http://www.spoj.pl/problems/PRIME1/から取得):

Input

The input begins with the number t of test cases in a single line (t<=10).
In each of the next t lines there are two numbers m and n (1 <= m <= n
<= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per
line, test cases separated by an empty line.

これが私のプログラムです：

#include <iostream>
using namespace std;

#define LLI long long int
#define sll(n) scanf("%lld",&n)
#define s(n) scanf("%d",&n)

int main()
{
    LLI m,n;
    int t,count=0;
    s(t);
    while(t--)
    {
        sll(m);
        sll(n);
        int a[32000]={0};
        int b[100005]={0};
        for(LLI i=2;i*i<=n;i++)
        {
            if(!a[i])
            {
                for(LLI j=i*i;j*j<=n;j=j+i)
                {
                    a[j]=1;
                }
                if(!(m%i))
                    b[0]=1;
                for(LLI j=i-(m%i);j<=n-m;j=j+i)
                {
                    if(m+j!=i)
                        b[j]=1;
                    }
                }
            }
            if(m==1)
                b[0]=1;
            for(LLI i=0;i<=n-m;i++)
            {
                if(!b[i]){
                    printf("%lld\n",m+i);
                    count++;
                }
            }
            printf("\n");
            printf("%d",count);
        }    
    return 0;
}
4

1 に答える 1

0

あなたのアルゴリズムは本当に奇妙です。
よく知られているふるい法を使用して、a[j]=1すべての複合材料を設定しますj。jあとは、必要な範囲のanyを出力するだけですa[j]==0。
しかし、代わりに、あなたはb配列を持っています。私はあなたがそれで何をしようとしているのか理解できません.

もう 1 つのポイントは、見つけた素数の数を出力して終了することです。
問題はそれを求めていないので、自動ジャッジはそれが原因で失敗する可能性が非常に高いです (この数は素数の 1 つと見なされますが、そうではありません)。

于 2012-05-24T13:57:33.297 に答える