11086  Composite Prime
Moderator: Board moderators

 New poster
 Posts: 3
 Joined: Thu Aug 24, 2006 9:20 am
I rather thank the problem setter.
I rather thank the problem setter.
Do you know why the system analyst gets high price than a programmer? Because, he has to specify the requirements of the software from his client
Do you know why the system analyst gets high price than a programmer? Because, he has to specify the requirements of the software from his client
This is mainly a problem solving site. I guess sometimes it is a problemsetter'smindreading site, we can't avoid that. But to praise someone for setting the problem that way?!?
If problem is simple then it's simple. If the statement is vague, that doesn't make the problem harder, it just makes the experience of solving it less satisfying.
This could've been a nice problem if the problem statement was written properly. I just hope it wasn't set that way on purpose.
moonstruck, I have no idea how you can even try to compare this to the "real world". Probably 95% of these problems are completely made up. Say this one, for example. Is it useful in any way? For it to be useful, you should be able to tell if a 500digit number is a composite prime and what are the primes that compose it, and do it efficiently, or something like that. Or all of those "guess the input format" type problems. That is realistic? I like the problem statements of the type "ya, ya, we know this is BS, but just play along". At least they don't pretend these translate into some "real life" problems.
There are challenges and then there are challenges. This type of problems I don't consider to be challenging, just annoying. Too bad this type of setting ruins the underlying problems, no matter how easy (or hard) they are.
Oh, I forgot my usual rant  in real world, I wouldn't be forced to use C to solve this problem. (Not that there is anything wrong with it)
If problem is simple then it's simple. If the statement is vague, that doesn't make the problem harder, it just makes the experience of solving it less satisfying.
This could've been a nice problem if the problem statement was written properly. I just hope it wasn't set that way on purpose.
moonstruck, I have no idea how you can even try to compare this to the "real world". Probably 95% of these problems are completely made up. Say this one, for example. Is it useful in any way? For it to be useful, you should be able to tell if a 500digit number is a composite prime and what are the primes that compose it, and do it efficiently, or something like that. Or all of those "guess the input format" type problems. That is realistic? I like the problem statements of the type "ya, ya, we know this is BS, but just play along". At least they don't pretend these translate into some "real life" problems.
There are challenges and then there are challenges. This type of problems I don't consider to be challenging, just annoying. Too bad this type of setting ruins the underlying problems, no matter how easy (or hard) they are.
Oh, I forgot my usual rant  in real world, I wouldn't be forced to use C to solve this problem. (Not that there is anything wrong with it)
This time it was an avoidthelamesymbolconfusion problem which was simply bad. With N used for 3 different things in the problem for no reason. Because of that it was not a vague problem it was just a wrong problem.
I personally think that interpreting a prompt even if it is vague is part of problem solving. Making a program that would work for every possible input case also is part of problem solving. But beating ambiguous and contradictory prompts isn't.
I personally think that interpreting a prompt even if it is vague is part of problem solving. Making a program that would work for every possible input case also is part of problem solving. But beating ambiguous and contradictory prompts isn't.
Yes problemsetter used N for three purposes.
1. Set of natural Number is N
2. Input Integer is N.
3. Constraints N <=2^20.
I think 3 is pointed to 2. Actually in two different puposes N is used.
This is not a problem at all. first N is in the problem description and 2nd N is in real problem I/O.
So i can say, to compare with real life problem it's trends us to make challenge.
1. Set of natural Number is N
2. Input Integer is N.
3. Constraints N <=2^20.
I think 3 is pointed to 2. Actually in two different puposes N is used.
This is not a problem at all. first N is in the problem description and 2nd N is in real problem I/O.
So i can say, to compare with real life problem it's trends us to make challenge.
I don't know why you thought that 2 and 3 refered to the same N, but anyway...
This ticked me off enough so I retried a buffered I/O until it finally worked! I thought that you couldn't use System.in.read(byte[],int,in), because I tried it before, but, it turns out, with buffer sizes that were too large. Actually, 2048 worked, 4096 didn't, I don't know if there is something in between.
There, beat Java time :P
(sorry for 40+ submitions)
This ticked me off enough so I retried a buffered I/O until it finally worked! I thought that you couldn't use System.in.read(byte[],int,in), because I tried it before, but, it turns out, with buffer sizes that were too large. Actually, 2048 worked, 4096 didn't, I don't know if there is something in between.
There, beat Java time :P
(sorry for 40+ submitions)
Re: I rather thank the problem setter.
So, you think a problem which is !(specific & simple),that is challenging?moonstruck wrote:If the problem is simple & specific, then where is our challenges?
!(specific & simple) = (!specific)  (!simple)
Ok, i am giving you a simple and (!specific) problem
#Find A+B where A>10 && B>10 (It's not typing mistake it's really A,B>10).
~~What is the challenge here. You can guess maximum A,B as 10^100 , 10^100000 or 10^10000000000........... Here,the !(specific) thing made it a boring guess game. Do u think programming contest is a guessing game contest?
Now, i am giving u a specific problem.
#Find hamilton cycle for a given simple graph where node can be at most 10000.
~~Everything specific here. Do you think there is no challenge in this problem?
Change your view,your life will be changed.
 CodeMaker
 Experienced poster
 Posts: 183
 Joined: Thu Nov 11, 2004 12:35 pm
 Location: AIUB, Bangladesh
i did not code this problem during the contest because of its poor description. i thought in the worst case i will be given 1 million(2^20) numbers, each of them can be as large as 2^31.
i knew what i have to do to solve it, but could not fit that limit neither in memory nor in time. i wondered that someone may have discovered a new formula. now i know what that formula is
only someone having the same experience will understand how painful it is.
i got AC by applying sieve on 2000000 , may be even less required.
i knew what i have to do to solve it, but could not fit that limit neither in memory nor in time. i wondered that someone may have discovered a new formula. now i know what that formula is
only someone having the same experience will understand how painful it is.
i got AC by applying sieve on 2000000 , may be even less required.
Jalal : AIUB SPARKS

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
11086  TLE
I'm having TLE for this code. anyone pls fix my probs. here is code.
Code: Select all
#include<stdio.h>
#include<math.h>
#define MAX 2000000
#define PRIME 0
#define NOTPRIME 1
unsigned char flag[MAX];
void seive()
{
int i,j,sq;
flag[0]=flag[1]=NOTPRIME;
flag[2] = PRIME;
sq = (int) sqrt(MAX);
for (i = 4; i < MAX; i += 2)
flag[i] = NOTPRIME;
for(i = 3; i < sq; i+= 2)
{
if(flag[i] == PRIME)
{
for(j = i*i; j < MAX; j+= i)
{
flag[j] = NOTPRIME;
}
}
}
}
int main()
{
int N,Nn,i,count,sq;
seive();
while(scanf("%d",&N)!=EOF)
{
count = 0;
while(N)
{
scanf("%d",&Nn);
sq = sqrt(Nn);
if(flag[Nn] == NOTPRIME)
{
for(i=2;i<=sq;i++)
{
if(flag[i] == PRIME && Nn%i == 0 && flag[Nn/i] == PRIME)
{
count++;
break;
}
}
}
}
printf("%d\n",count);
}
return 0;
}

 New poster
 Posts: 32
 Joined: Tue Feb 13, 2007 1:31 pm
Re: 11086  Composite Prime
test case
answer
Code: Select all
5
999997 999998 999999 1000000 1000001
Code: Select all
2
Re: 11086  Composite Prime
I am getting TLE.plzz help me...
thanks in advance.
Code: Select all
#include<stdio.h>
#define MAX 1048580
bool isnp[MAX+3],cp[MAX+3];
int main()
{
long int i,j,p,n,c,flag,b,x;
isnp[1]=isnp[0]=true;
for(i=2;i*i<=MAX;i++)
{
if(!isnp[i])
{
for(j=i*i;j<=MAX;j+=i)
isnp[j]=true;
}
}
while(scanf("%ld",&n)==1)
{
x=0;
for(i=0;i<n;i++)
{
scanf("%ld",&b);
if(b==0  b==1)
cp[b]=false;
else if(isnp[b]==false)
{
cp[b]=false;
}
else
{
flag=0;
for(j=2;(j*j)<=b;j++)
{
c=0;
if(b%j==0)
{
p=b/j;
c=1;
}
if(c==1 && (isnp[j]==true  isnp[p]==true))
{
flag=1;
break;
}
}
if(flag==1)
cp[b]=false;
else
cp[b]=true;
}
if(cp[b]==true)
x++;
}
printf("%ld\n",x);
}
return 0;
}
Re: 11086  Composite Prime
You will never get acc with this method.
Try to use a faster method to pass this. You need to learn more about primes.
Try to use a faster method to pass this. You need to learn more about primes.
try_try_try_try_&&&_try@try.com
This may be the address of success.
This may be the address of success.

 Experienced poster
 Posts: 136
 Joined: Sat Nov 29, 2008 8:01 am
 Location: narayangong,bangladesh.
 Contact:
11086  Composite Prime
what is the number of composite prime less than 2^20(1048556).Is it 227886??
Life is more complicated than algorithm.
http://felixhalim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com
http://felixhalim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com