Re: smallest positive integer that has exactly k divisors

mukesh tiwari said:

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 .

Here's a solution for the first 36 values of k.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv)
{
unsigned long k = 0;
if(argc > 1 && (k = strtoul(argv[1], NULL, 10)) > 0 && k < 37)
{
unsigned long solution[] =
{
1, 2, 4, 6,
16, 12, 64, 24,
36, 48, 1024, 60,
4096, 192, 144, 120,
65536, 180, 262144, 240,
576, 3072, 4194304, 360,
1296, 12288, 900, 960,
268435456, 720, 1073741824, 840,
9216, 196608, 5184, 1260
};
printf("%lu\n", solution[k - 1]);
}
else
{
fprintf(stderr, "Spec a number in the range 1-36, or\n");
fprintf(stderr, "write some more code.\n");
}
return 0;
}

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
.

Relevant Pages