Posted:

**Mon Sep 11, 2006 5:08 pm**ok i understood...

so apply sieve of eratosthenes...????

so apply sieve of eratosthenes...????

The UVa Online Judge board

https://uva.onlinejudge.org/board/

https://uva.onlinejudge.org/board/viewtopic.php?f=33&t=11922

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

Posted: **Mon Sep 11, 2006 5:08 pm**

ok i understood...

so apply sieve of eratosthenes...????

so apply sieve of eratosthenes...????

Posted: **Tue Sep 12, 2006 9:42 am**

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

Posted: **Tue Sep 12, 2006 5:14 pm**

This is mainly a problem solving site. I guess sometimes it is a problem-setter's-mind-reading 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 500-digit 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 500-digit 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)

Posted: **Tue Sep 12, 2006 8:08 pm**

so from ur point of view it's a challenging problem , what's the challenge , to write a simpleIf the problem is simple & specific, then where is our challenges?

sieve without any optimization.

Posted: **Tue Sep 12, 2006 9:30 pm**

This time it was an avoid-the-lame-symbol-confusion 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.

Posted: **Wed Sep 13, 2006 7:56 am**

Yes problem-setter 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.

Posted: **Thu Sep 14, 2006 6:43 pm**

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)

Posted: **Fri Sep 15, 2006 12:03 am**

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?

Posted: **Fri Sep 15, 2006 8:25 pm**

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.

Posted: **Sat Nov 25, 2006 10:07 pm**

EDIT : ACed....

Posted: **Sat Jun 21, 2008 1:11 pm**

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

Posted: **Thu Jan 15, 2009 11:45 pm**

test case
answer

Code: Select all

```
5
999997 999998 999999 1000000 1000001
```

Code: Select all

```
2
```

Posted: **Tue Mar 17, 2009 7:46 pm**

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

Posted: **Wed Mar 18, 2009 7:03 am**

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.

Posted: **Sat Oct 23, 2010 9:11 pm**

what is the number of composite prime less than 2^20(1048556).Is it 227886??