11086 - Composite Prime

[vinay]

ok i understood...
so apply sieve of eratosthenes...????

[moonstruck]

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

[Darko]

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)

[Rainy Day]

If the problem is simple & specific, then where is our challenges?

so from ur point of view it's a challenging problem , what's the challenge , to write a simple
sieve without any optimization.

[Vexorian]

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.

[rabby]

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.

[Darko]

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)

[Sumon]

If the problem is simple & specific, then where is our challenges?

So, you think a problem which is !(specific & simple),that is challenging?

!(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?

[CodeMaker]

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.

[jan_holmes]

EDIT : ACed....

[nahid]

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

[deadangelx]

test case

Code: Select all

5
999997 999998 999999 1000000 1000001

answer

Code: Select all

2

[Bitta]

I am getting TLE.plzz help me...

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

thanks in advance.

[Obaida]

You will never get acc with this method.
Try to use a faster method to pass this. You need to learn more about primes.

[sazzadcsedu]

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