Re: smallest positive integer that has exactly k divisors

On Wed, 24 Oct 2007 18:30:18 +0000 (UTC), mukesh tiwari 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 factors until
factors are equal to the k but this one is taking to much time even
for 2000 factors .

If you write the factorization of N as the product of powers of
distinct primes, and the powers are W, X, Y, ... , then the
number of divisors of N is (W+1)*(X+1)*(Y+1)*... .

So if you want the smallest positive integer with k divisors,
I'd suggest exploring ways of writing k as k = (W+1)*(X+1)* ... ,
and then using the smallest primes as the bases of those powers:
2**W * 3**X * 5**Y * ... (assuming, here, that W <= X <= Y).

So, if k is prime, the number you want is a power of 2.

If k has many factors, you'll have flexibility in assigning
those factors to W+1, X+1, Y+1, et cetera: there's no rule
saying that all the 3's (say) have to stay together. So,
for example, for k = 9, you might say 9 = (2+1)*(2+1),
leading to 2**2 * 3**2 = 36 as your number with 9 factors;
or you might say 9 = (8+1), leading to 2**8 = 256 as your
number with 9 factors. I haven't thought this through far
enough to know how to choose best among these choices.

HTH

--
To email me, substitute nowhere->spamcop, invalid->net.

.

Relevant Pages
Loading