Posted:

**Sun Oct 09, 2005 3:34 pm**

you may post your code

you may post your code

Page **2** of **2**

Posted: **Sun Oct 09, 2005 3:34 pm**

you may post your code

Posted: **Fri Nov 25, 2005 1:56 pm**

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

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.

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;
}
```

Posted: **Sat Nov 26, 2005 5:26 pm**

the number will be at best 9999*10000 .

so how do you check prime if the number will be greater then 300000000?

so how do you check prime if the number will be greater then 300000000?

Posted: **Tue Dec 06, 2005 6:51 pm**

Do you mean "300000000" or "30000000" ?bijon wrote:the number will be at best 9999*10000 .

so how do you check prime if the number will be greater then 300000000?

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**

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 siv**ing** as many as you can, and use the *normal* method to check for primes for larger numbers.

*normal*.. check divisibility upto sqrt(n).

There can be numbers as large as 300000000 ( 3 * 10^8 )..

.. but you can't get that much memory to store all those..

.. try siv

Posted: **Thu Nov 05, 2009 8:02 pm**

Weak test!!!!

For such test:

1

10000 10000 100000.....10000

My program should get MLE! But it got AC!

For such test:

1

10000 10000 100000.....10000

My program should get MLE! But it got AC!