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

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

11086 - Composite Prime

Post by Sumon » Sun Sep 10, 2006 7:41 am

After long time i got a number theory problem with such an undefined statement like "N integers are positive-natural numbers". What does natural number means? Shall we try upto INFINITY?? Would you please tell me what would be the trouble if you had specified it with specific number. By the way i got this problem accepted and still confused about it's data range. Pathetic?!!?
Change your view,your life will be changed.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Sun Sep 10, 2006 9:53 am

I'm pretty sure the input numbers are less than 5,000,000
Otherwise my program will crash.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Sep 10, 2006 10:21 am

The capital letter N is used in three different ways in this problem:
the set of natural numbers is normally denoted by N
First line of each test case contains one integer N.
Constraints
- N ≤ 2^20
Al three are different, and the last one is not the number of input values per case, but the input value itself.
At least that is how I interpret it, and I got AC with it....

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Sun Sep 10, 2006 3:58 pm

little joey wrote:Al three are different, and the last one is not the number of input values per case, but the input value itself.
At least that is how I interpret it, and I got AC with it....
Despite I've interpreted it in the same way finally, imho the problem statement says something different :evil:

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

need some explaination

Post by Rocky » Sun Sep 10, 2006 3:59 pm

i cant understand the problem..
can any one explain it with i/o ... plssss it will help mee

thank's in advance
rocky

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: need some explaination

Post by Martin Macko » Sun Sep 10, 2006 4:05 pm

Rocky wrote:i cant understand the problem..
can any one explain it with i/o ... plssss it will help mee
I can give you an example of few first composite primes: 4, 6, 9, 10, 14, ...

The numbers 1, 2, 3, 5, 7, 11, 13 are not composite, therefore they are not composite primes. The numbers 8 and 12 have nontrivial composite divisors (eg. 4), so they are not composite primes, too.

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

help again

Post by Rocky » Sun Sep 10, 2006 4:14 pm

thank's for reply]
actually i want the explain with the problem i/o...
can you help plsss with the problem i/o..

thank's in advance
rocky

User avatar
Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

soory

Post by Rocky » Sun Sep 10, 2006 4:19 pm

ahh got it ... i think more deeply for this and in another way it is simpleee..

thanks
rocky

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

Post by Vexorian » Sun Sep 10, 2006 4:44 pm

I barely could have 9 secons there, I think the problem should state an actual limit so we would now if we could use a table or something.

Shahidul Islam (SUST)
New poster
Posts: 1
Joined: Sun Sep 10, 2006 7:34 pm

Post by Shahidul Islam (SUST) » Sun Sep 10, 2006 8:36 pm

little joey wrote:The capital letter N is used in three different ways in this problem:
the set of natural numbers is normally denoted by N
First line of each test case contains one integer N.
Constraints
- N ≤ 2^20
Al three are different, and the last one is not the number of input values per case, but the input value itself.
At least that is how I interpret it, and I got AC with it....
Thank you little joey. May be i am not good at guessing and solved this problem for data range 2^31-1. Your assumtion allowed me to get accepted in time 1.182 sec.
Looking at the progammers who gets TLE in 100(3n+1), I feel how good good programmer I am and looking at the programmer get ACC in 10757(Interpreting SQL) i feel how bad I am.

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

Post by rabby » Mon Sep 11, 2006 7:49 am

You have to find the Composite Prime for M. M is the Subset of N. N is the set of natural number and N<=2^20.
So what it means:: Test case is N (Natural number and <=2^20). Then following N integers are positive-natural numbers (difference between positive-natural numbers and natural numbers is '0'). So all N input values are positive natural numbers means greater than 0 and less then or equal to N (N<=2^20).
[quote]

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

confused

Post by vinay » Mon Sep 11, 2006 2:00 pm

can someone explain what elements come in the set, I can't figure out the symbol between x and y , is it multiplication????
A number m is a member of M if m = x*y where x > 1 and y > 1. Both x and y are natural numbers.
:oops:
If I will myself do hashing, then who will do coding !!!

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

Post by rabby » Mon Sep 11, 2006 2:56 pm

Yeah!! *=Multiplication :)

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 3:43 pm

sorryy... i misunderstood the statement... :oops: :oops:
If I will myself do hashing, then who will do coding !!!

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 4:57 pm

ca anybody explain the answer for the answer for the first test case :cry:
If I will myself do hashing, then who will do coding !!!

Post Reply

Return to “Volume 110 (11000-11099)”