0

spoj.pl n codechef.com 中的“Prime 生成器”存在问题。我已经成功解决了它，但即使尝试了很多也没有提交。请帮忙。我得到一个错误的答案，即使我认为它是正确的。它满足了我所知道的所有案例。问题陈述是（取自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所需范围内的任何内容，其中a[j]==0.
但相反，你有b数组，我就是不明白你想用它做什么。

另一点是您以打印您找到的素数的数量结束。
问题并没有要求它，因此自动法官很可能因此而使您失望（它会将这个数字视为质数之一，而事实并非如此）。

于 2012-05-24T13:57:33.297 回答