Re: smallest positive integer that has exactly k divisors

On Oct 23, 11:11 pm, "mensana...@xxxxxxxxxxx" <mensana...@xxxxxxx>
wrote:
On Oct 24, 12:20?am, mukesh tiwari <mukeshtiwari.ii...@xxxxxxxxx>
wrote:

Hello everybody . i have to find the smallest positive integer that
has exactly k divisors. for example if k=6 then 12 is the minimum
number which have 6 divisors.One brute force approach i came across
is find the prime factorization and calculate the divisors until
divisors are equal to the k but this one is taking to much time even
for 2000 factors .

## On Oct 24, 12:20 am, mukesh tiwari <mukeshtiwari.ii...@xxxxxxxxx>
wrote:
## > Hello everybody . i have to find the smallest positive integer
that
## > has exactly k divisors. for example if k=6 then 12 is the
minimum
## > number which have 6 divisors.
## > One brute force approach i came across
## > is find the prime factorization and calculate the divisors
until
## > divisors are equal to the k but this one is taking to much time
even
## > for 2000 factors .
##
## Did you really mean 2000 factors? You do know that the
## number of divisors is 2**factors, don't you?

Really? Then how can 12 have 6 divisors? (6 is not a power of 2.)

This is true, _if_ N is square-free (i.e., when 1 is the only perfect
square which divides into N with no remainder).

***

To do this algorithmically, you would need to look at all possible
factorizations of 2000, and given such a factorization

a(1) * a(2) * ... * a(k),

where a(1) >= a(2) >= ... >= a(k), you look at the number

2^[a(1)-1] * 3^[a(2)-1] * ... * p(k)^[a(k)-1],

where p(k) is the kth prime. This is the smallest number of the form

q(1)^[a(1)-1] * q(2)^[a(2)-1] * ... * q(k)^[a(k)-1],

where q(1), q(2), ..., q(k) are distinct primes. (I think.) Then you
would take the minimum of all of these numbers. There might be a
faster way, though, which I can't think of, right at the moment.

--- Christopher Heckman

.

Relevant Pages
Loading