10871 - Primed Subsequence

[bijon]

you may post your code

[Niaz]

Posting my code that gives correct ans for the bijon's given input.

Code: Select all

#include<stdio.h>
#include<math.h>
#define max 10011
#define pmax 20000010
char prime[pmax];
int bank[max+100];
int isPrime(long);
void siv()
{
    long i,j,k;
    prime[0]='x';
    prime[1]='x';
    for(i=3;i<=(int)sqrt(pmax);i=i+2)
    {
        if(prime[j]!='x')
        {
            k=i;
            j=k+2*k;
            while(j<=pmax-5)
            {
                prime[j]='x';
                j=j+2*k;        
            }
        }
    }
}
int isPrime(long a)
{
    if(a==2)
        return 1;
    if(a%2!=0)
        if(prime[a]!='x')
            return 1;
    return 0;
}
int main()
{
    int N,n,i,j,sum,s,e;
    siv();
    //freopen("F:\\input.in","r",stdin);
    //freopen("C:\\output.out","w",stdout);
    scanf("%d",&N);
    while(N--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d",&bank[i]);
        s=0;
        e=10011;
        for(i=0;i<n;i++)
        {
            sum=0;
            for(j=i;j<n;j++)
            {
                sum=sum+bank[j];
                if(isPrime(sum) && i!=j)
                {
                    if(j-i<e-s)
                    {
                        s=i;
                        e=j;
                    }
                    
                }
            }
        }
        if(e!=10011)
        {
            printf("Shortest primed subsequence is length %d:",e-s+1);
            for(i=s;i<=e;i++)
                printf(" %d",bank[i]);
            printf("\n");
        }
        else
        {
            printf("This sequence is anti-primed.\n");    
        }
    }
    return 0;
}

If anyone can find my mistake then I will be very much grateful to him. This problem is making me crazy. Plz help me. Anyway, thanks in advance.

[bijon]

the number will be at best 9999*10000 .
so how do you check prime if the number will be greater then 300000000?

[Niaz]

the number will be at best 9999*10000 .
so how do you check prime if the number will be greater then 300000000?

Do you mean "300000000" or "30000000" ?

I got to know from a previous post on this problem that the number will not be too large. That's why I took such a small upper limit. Would you please tell me the upper limit for my SIV ?

Thanks.

[sohel]

AFAIR,

There can be numbers as large as 300000000 ( 3 * 10^8 )..
.. but you can't get that much memory to store all those..

.. try siving as many as you can, and use the normal method to check for primes for larger numbers.

normal.. check divisibility upto sqrt(n).

[Igor9669]

Weak test!!!!
For such test:
1
10000 10000 100000.....10000
My program should get MLE! But it got AC!