Need your help

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Need your help

Post by Giorgi »

Here is problem:
Given 10 integer numbers: a1,a2..a10
each number less than 1000.
s=a1*a2..*a10.
Find how many divisors has s?

I found all prime divisors of s. An need your help to find out how many different numbers I can get multiplying those prime divisors?
For example if we have: 2,2,3,3 we can get 8 numbers:
2,4,3,6,9,12,18,36.
I think there will be formula but I don't know it.

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh »

After factorization you have

s = p1^x1 * p2^x2 * p3^x3 * ... * pn^xn where pn are all distinct primes.

Then the number of unique factors is

(x1+1)*(x2+1)*(x3+1)*...*(xn+1)

Your example is actually 2^2*3^2 so the answer is (2+1)*(2+1) = 9 and there are 9 divisors (you forgot 1, which is also a divisor).

The reasoning is that for every prime p with multiplicity x, you can take from 0 to x = x+1 possible powers of the prime (p^0,p^1,...,p^x).

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

Post by Giorgi »

Thank you:)

Post Reply

Return to “Algorithms”