English 中文(简体)
许多在线法官的初级发电机方案,即使经过多次尝试,也得不到接受
原标题:Program of prime generators in many online judges not getting accepted even after trying a lot
  • 时间:2012-05-24 13:18:36
  •  标签:
  • c++

There is a problem "Prime generators" in spoj.pl n codechef.com. I have successfully solved it but it is not getting submitted even after trying a lot. Please help. I am getting a wrong answer even though I think it is correct. It is satisfying all the cases known to me. The problem statement is (taken from 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
",m+i);
                    count++;
                }
            }
            printf("
");
            printf("%d",count);
        }    
    return 0;
}
问题回答

Your algorithm is really weird.
You use the well-known sieve method, setting a[j]=1 for every composite j. Now all you should do is print any j in the desired range, for which a[j]==0.
But instead, you have the b array, and I just can t understand what you re trying to do with it.

Another point is that you end by printing the number of primes you ve found.
The problem didn t ask for it, so an automated judge is very likely to fail you because of it (it will consider this number as one of the primes, and it isn t).





相关问题
Undefined reference

I m getting this linker error. I know a way around it, but it s bugging me because another part of the project s linking fine and it s designed almost identically. First, I have namespace LCD. Then I ...

C++ Equivalent of Tidy

Is there an equivalent to tidy for HTML code for C++? I have searched on the internet, but I find nothing but C++ wrappers for tidy, etc... I think the keyword tidy is what has me hung up. I am ...

Template Classes in C++ ... a required skill set?

I m new to C++ and am wondering how much time I should invest in learning how to implement template classes. Are they widely used in industry, or is this something I should move through quickly?

Print possible strings created from a Number

Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad. i.e. for 1,0-> No Letter for 2->...

typedef ing STL wstring

Why is it when i do the following i get errors when relating to with wchar_t? namespace Foo { typedef std::wstring String; } Now i declare all my strings as Foo::String through out the program, ...

C# Marshal / Pinvoke CBitmap?

I cannot figure out how to marshal a C++ CBitmap to a C# Bitmap or Image class. My import looks like this: [DllImport(@"test.dll", CharSet = CharSet.Unicode)] public static extern IntPtr ...

Window iconification status via Xlib

Is it possible to check with the means of pure X11/Xlib only whether the given window is iconified/minimized, and, if it is, how?

热门标签