Error In Solution

[aravindkp_sof]

the Following is the solution of the problem Prime generator(problem code : PRIME1). I encountered an error while submitting the solution. kindly help me out !

[code]#include<stdio.h>
#include<stdlib.h>
long checkprime(long num)
{
    long i;
    for(i=2;i<=num/2;i++)
    {
        if(num % i == 0)
        {
            return 0;
            break;
        }
    }
}
int main()
{
    int tst,res;
    long int *ptr1,*ptr2,i,k;
    scanf("%d",&tst);
    ptr1=(long int*)malloc(tst*sizeof(long int));
    ptr2=(long int*)malloc(tst*sizeof(long int));
    for(i=0;i<tst;i++)
    {
        scanf("%ld%ld",ptr1+i,ptr2+i);
    }
    for(k=0;k<tst;k++)
    {
            for(i=*(ptr1+k);i<=*(ptr2+k);i++)
        {
            res=checkprime(i);
            if(res != 0)
                printf("\n%ld",i);
        }
        printf("\n\n");

}
return 0;
}[/code]

[leppyr64]

Please use code tags when posting code.

What kind of error do you receive?

[aravindkp_sof]

i recieve a compilation error!

[leppyr64]

What compiler are you submitting to? When you receive a compilation error you can click on where it says "Compilation Error" and it will tell you what the compiler returned.

I submitted this to the C and both C++ compilers and it did not return compilation error.

[aravindkp_sof]

When I submit the answer on spoj it returns an error. The code works fine on my compiler too.i used the gcc compiler!!!

[leppyr64]

Your last submission says that you got Wrong Answer, that's not an error. That means that your code did not return what the judge was expecting.

Why aren't your returning anything from checkprime?

[aravindkp_sof]

I am a pure begineer in programming please help me out..i don't understand what is wrong with my code!!

[leppyr64]

This is probably not the best problem to start with. Solve TEST first.

[aravindkp_sof]

Can you please point out the error in my code.that wiil be realy helpful!
I am gonna try to solve test..very soon

[leppyr64]

The most obvious thing that I notice is that checkprime should have a return 1 at the end of it. Even if you fix the wrong answer then you will get time limit exceeded. Your algorithm is far too slow for the worst possible test case.

[aravindkp_sof]

can you suggest a better algorithm ?
is their a problem in the output format?

[leppyr64]

Your current definition of a prime is "a number that is not divisible by a number less than itself". That means that in the worst case you will need n^2 operations to check a list of n numbers. You need to simplify this definition.

[aravindkp_sof]

I edited the code as following Got the Output but yields a 'Wrong answer' on spoj!

#include<stdio.h>
#include<math.h>
long prime(long num)
{
    long i,sqr;
    if(num == 2)
        return 1;
    else if(num %2 ==0 )
    return 0;
    else if(num ==3)
        return 1;
    else if(num % 3 == 0)
        return 0;
    else
    {   sqr=sqrt(num);
        for(i=2;i<=sqr;i+=2)
        {
            if(num % i == 0)
            {
                return 0;
                break;
            }
        }
}
}
int main()
{
    int n,i,res;
    long j,num1[12],num2[12];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%ld%ld",&num1[i],&num2[i]);
        for(j=num1[i];j<=num2[i];j++)
        {
            res=prime(j);
            if(res != 0)
                printf("%ld\n",j);
        }
        printf("\n");
    }
}

[leppyr64]

There are many instances where your function prime does not return a controlled value. At the end of it you should return 1.

There is one number that could appear in the input that you have not accounted for.

[leppyr64]

This solution will reduce your runtime greatly but will still not be enough to get accepted.

You have updated your definition of a prime to be "not divisible by up a number less than or equal to it's square root". You can simplify this further.

[aravindkp_sof]

i edited the code as follows but it still gives 'Wrong Answer' But yields correct output!
Link to Output:http://ideone.com/61c0rO
code:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
long prime(long num)
{
    long i,sqr;
    if(num ==1)
        return 0;
    else if(num == 2)
        return 1;
    else if(num %2 ==0 )
        return 0;
    else if(num ==3)
        return 1;
    else if(num % 3 == 0)
        return 0;
    else
    {   sqr=sqrt(num);
        for(i=2;i<=sqr;i+=3)
        {
            if(num % i == 0)
            {
                return 0;
                break;
            }
        }
    }
    return 1;
}
int main()
{
    int tst,res;
    long int *ptr1,*ptr2,i,k;
    scanf("%d",&tst);
    ptr1=(long int*)malloc(tst*sizeof(long int));
    ptr2=(long int*)malloc(tst*sizeof(long int));
    for(i=0;i<tst;i++)
    {
        scanf("%ld%ld",ptr1+i,ptr2+i);
        for(k=*(ptr1+i);k<=*(ptr2+i);k++)
            {
                res=prime(k);
                if(res != 0)
                    printf("%ld\n",k);
            }
            printf("\n");
    }

return 0;
}

[leppyr64]

Your algorithm is not accurate. Your code returns far too many prime numbers.