Re: smallest positive integer that has exactly k divisors


Gerry Myerson wrote:
In article <1193203237.965221.68120@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
mukesh tiwari <mukeshtiwari.iiitm@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 .

Do you know the formula for the number of divisors of n,
given the prime factorization of n?
Can you set that formula equal to k and thus find which kinds
of prime factorization will lead to a number with exactly k divisors?

For example, do you know that for a number to have exactly 7 divisors,
the number must be the 6th power of a prime?

--
Gerry Myerson (gerry@xxxxxxxxxxxxxxx) (i -> u for email)

yes i know the formula for number of divisprs of n.
n=p1^e1*p2^2*........pm^em
then number of divisors will be (e1+1)*(e2+1)......(em+1).
quote "Can you set that formula equal to k" .
but i have to know in advance that how many primes will sufficient
for given problem statement.
Plz explain bit more your method . thnkx for reply.

.

Relevant Pages

  • Re: ISO algorithm to list all divisors of a number
    ... I'm looking for an algorithm to list all the divisors (not ... >necessarily prime) of an arbitrary positive integer. ... >all the divisors, but I'm looking for an algorithm with a clue. ... First find the prime factorization of the number. ...
    (sci.math)
  • Re: Number of factors/divisors question
    ... You can find the number of divisors from ... So the number of positive divisors in your restricted sense is ... --- Calvin ...
    (sci.math)
  • Re: smallest positive integer that has exactly k divisors
    ... number which have 6 divisors.One brute force approach i came across ... is find the prime factorization and calculate the factors until ... distinct primes, and the powers are W, X, Y, ... ... So if you want the smallest positive integer with k divisors, ...
    (sci.math.research)
  • Re: smallest positive integer that has exactly k divisors
    ... number which have 6 divisors.One brute force approach i came across ... is find the prime factorization and calculate the divisors until ... square-free just means the UNIQUE divisors will be the same ...
    (sci.math)
  • Re: smallest positive integer that has exactly k divisors
    ... number which have 6 divisors.One brute force approach i came across ... is find the prime factorization and calculate the divisors until ... Gerry Myerson ...
    (sci.math)
Loading