## 11086 - Composite Prime

Moderator: Board moderators

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

### 11086 - Composite Prime

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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I'm pretty sure the input numbers are less than 5,000,000
Otherwise my program will crash.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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....

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
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

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

### need some explaination

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

rocky

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

### Re: need some explaination

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.

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

### help again

actually i want the explain with the problem i/o...
can you help plsss with the problem i/o..

rocky

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

### soory

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
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
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
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]

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

### confused

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.
If I will myself do hashing, then who will do coding !!!

rabby
New poster
Posts: 3
Joined: Mon Sep 11, 2006 7:39 am
Yeah!! *=Multiplication

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
sorryy... i misunderstood the statement...
If I will myself do hashing, then who will do coding !!!

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
ca anybody explain the answer for the answer for the first test case
If I will myself do hashing, then who will do coding !!!