Divisors from Prime Factors

tanvi.azgaonkar · #1 $Old$ November 1st, 2009, 06:44 PM

Hello all,

Suppose I have prime factors of a number , from the prime factors how can I find distinct divisors of a number.

Eg :
12 = 2*2*3 ( I have 2,2,3 as prime factors )

I need to find divisors of 12 or atleast Number of distinct divisors of 12 ( 4 in this case )
2,3,4,6

umgambit · #2 $Old$ November 1st, 2009, 07:48 PM

Well, if n is decomposed as
$n=p1^{\alpha_1}p_2^{\alpha 2}\dots p_k^{\alpha_k}$
all divisors of n are of the form
$n=p1^{\beta_1}p_2^{\beta 2}\dots p_k^{\beta_k}$
where
$0\leq \beta_j\leq \alpha_j$
Note that
$\beta_j has(\alpha_j+1)$
possible values, hence the total number of divisors of n is
$(\alpha_1+1)(\alpha_2+2)...(\alpha_k+1)$
For example 12=2^2.3^1
$\alpha_1=2,\alpha_2=1$
and 12 has (2+1)(1+1)=6 divisors: 1,2,3,4,6,12.

tanvi.azgaonkar · #3 $Old$ November 2nd, 2009, 07:40 PM

(a1 + 1)(a2 + 2)..... (ak + 1)
are you sure (a2+2) or (a2+1) ?
also assuming its all additive to 1
say 16 = 2^4;
whats the number of divisors from this method ?

Tanvi

Thanks lot for the head start !

umgambit · #4 $Old$ November 3rd, 2009, 02:39 AM

Of course, I meant (a2+1), it's a typo-

For 16=2^4:

you only have one alpha: alpha_1=4, hence (4+1) divisors: 1,2,4,8, and 16.

Greetings

tanvi.azgaonkar · #5 $Old$ November 3rd, 2009, 08:42 AM

Thanks it helped !!