Castor and Pollux
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 745
Solved: 220
- Description
- Castor and Pollux were twin brothers, however Castor always seemed to get the better of Pollux. One day Castor posed this challenge to Pollux:
.
Castor: Dear brother, I don't think you can tell me the number of divisors a number has.
Pollux: Surely I can, just tell me the number.
Castor: Not so fast, I am more interested in the way that you come to your answer than the answer yourself, so you need to write me a program to do it.
Pollux: Ok, then my program will just loop through all the smaller numbers and see if they divide it. So if the number were 6 then my program would say that 1 divides 6, 2 does also, 3 does too, but four and five don't.
Castor: Surely that will work, but I plan on giving your program numbers as large as 1,000,000,000 and up to a 1,000 of them.
Pollux: Hmm, my program will take quite a while to produce an answer.
Castor: Yes, and that is not acceptable.
Pollux: I guess I could write a better program. Maybe if I factor the number first.
Castor: How would that go?
Pollux: Well, first I can get a list of all the prime factors. Each divisor either contains the prime factor in its factorization or doesn't. For example the prime factors of 30 are 2, 3, and 5. 10 is a divisor and it contains 2 and 5 as divisors.
Castor: And how does this help?
Pollux: Well each divisor corresponds to a subset of the prime factors. 10 corresponds to {2,5}.
Castor: I see now.
Pollux: And I know that there are always 2^n subsets of a given set.
Castor: Well, you had better get to coding!
Pollux: This may not help.
- Input
- There will be several test cases.
Each case will consist of a single line with a positive integer, N, less than 1,000,000,000.
- Output
- For each integer output a single line containing "There are M divisors of N."
- sample input
-
6 30 7 175883251
- sample output
-
There are 4 divisors of 6. There are 8 divisors of 30. There are 2 divisors of 7. There are 8 divisors of 175883251.
- hint
- source