Page 2 of 2

Posted: Sun Oct 09, 2005 3:34 pm
by bijon

you may post your code

Posted: Fri Nov 25, 2005 1:56 pm
by 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.

Posted: Sat Nov 26, 2005 5:26 pm
by bijon
the number will be at best 9999*10000 .
so how do you check prime if the number will be greater then 300000000?

Posted: Tue Dec 06, 2005 6:51 pm
by Niaz
bijon wrote: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.

Posted: Wed Dec 07, 2005 10:09 am
by 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).

Re: 10871 - Primed Subsequence

Posted: Thu Nov 05, 2009 8:02 pm
by Igor9669
Weak test!!!!
For such test:
1
10000 10000 100000.....10000
My program should get MLE! But it got AC!