## 10871 - Primed Subsequence

Moderator: Board moderators

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:
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='x';
prime='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.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

bijon
New poster
Posts: 18
Joined: Thu Jan 06, 2005 2:12 pm
the number will be at best 9999*10000 .
so how do you check prime if the number will be greater then 300000000?

Niaz
Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh
Contact:
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.
Please join The ACM Solver Group at Yahoo
http://groups.yahoo.com/group/acm_solver/

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 10871 - Primed Subsequence

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