11086 - Composite Prime

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay » Mon Sep 11, 2006 5:08 pm

ok i understood...
so apply sieve of eratosthenes...???? :lol:
If I will myself do hashing, then who will do coding !!!

moonstruck
New poster
Posts: 3
Joined: Thu Aug 24, 2006 9:20 am

I rather thank the problem setter.

Post by moonstruck » 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

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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)

Rainy Day
New poster
Posts: 8
Joined: Sun Sep 10, 2006 9:03 am

Post by Rainy Day » Tue Sep 12, 2006 8:08 pm

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. :-? :D :)

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am

Post by Vexorian » 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.

rabby
New poster
Posts: 3
Joined: Mon Sep 11, 2006 7:39 am

Post by rabby » 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.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » 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)

Sumon
New poster
Posts: 17
Joined: Fri May 30, 2003 8:14 pm
Location: Bangladesh
Contact:

Re: I rather thank the problem setter.

Post by Sumon » Fri Sep 15, 2006 12:03 am

moonstruck wrote: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?
Change your view,your life will be changed.

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » 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 :x

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

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Post by jan_holmes » Sat Nov 25, 2006 10:07 pm

EDIT : ACed.... :)

User avatar
nahid
New poster
Posts: 18
Joined: Wed Oct 04, 2006 8:59 pm
Location: DHAKA,BANGLADESH
Contact:

11086 - TLE

Post by nahid » 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;
}

deadangelx
New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

Re: 11086 - Composite Prime

Post by deadangelx » Thu Jan 15, 2009 11:45 pm

test case

Code: Select all

5
999997 999998 999999 1000000 1000001
answer

Code: Select all

2

Bitta
New poster
Posts: 4
Joined: Fri Jan 25, 2008 7:04 pm
Location: Dhaka,Bangladesh
Contact:

Re: 11086 - Composite Prime

Post by Bitta » Tue Mar 17, 2009 7:46 pm

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
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11086 - Composite Prime

Post by Obaida » 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_try_try_try_&&&_try@try.com
This may be the address of success.

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

11086 - Composite Prime

Post by sazzadcsedu » Sat Oct 23, 2010 9:11 pm

what is the number of composite prime less than 2^20(1048556).Is it 227886??
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

Post Reply

Return to “Volume 110 (11000-11099)”