Re: smallest positive integer that has exactly k divisors

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?
##
## So it shouldn't surprise you that finding
## 1148130695274254524232833201177681984022317702088695
## 2004776427368257662613923703138566594863165062699184
## 4596463898746277344711896086305533142593135616665318
## 5391299891453122800006887791482400448714289269900634
## 8624478161546364638836394731702604046635397090499655
## 8162398808944629605623311649536164221970332681344168
## 9089844585056023794848079140589009347765004290027167
## 0662583052200813223628129176126788331720659899539641
## 8127021779858404042159853183251540889433902091920554
## 9577835896720391600819572166305827553804255837260155
## 2834878641943205450891527578388262517543552880082284
## 2770817965453762184851149029376 divisors is a labor
## intensive process.


# Python
#
# all the divisors of a more realistic set of factors
#
import gmpy
factors = [5,7,11,13,17] # a list of 5 factors
for i in xrange(2**len(factors)):
divisor_pattern = gmpy.digits(i,2).zfill(5) # binary number
product = 1
print divisor_pattern,
divisor_factors = []
for f,g in enumerate(divisor_pattern):
if g == '0': # factor present
product *= factors[f]
divisor_factors.append('%2s' % (factors[f]))
else: # 1 if factor not present
divisor_factors.append(' 1')
print '%6d %s' % (product,' * '.join(divisor_factors))

## 00000 85085 5 * 7 * 11 * 13 * 17
## 00001 5005 5 * 7 * 11 * 13 * 1
## 00010 6545 5 * 7 * 11 * 1 * 17
## 00011 385 5 * 7 * 11 * 1 * 1
## 00100 7735 5 * 7 * 1 * 13 * 17
## 00101 455 5 * 7 * 1 * 13 * 1
## 00110 595 5 * 7 * 1 * 1 * 17
## 00111 35 5 * 7 * 1 * 1 * 1
## 01000 12155 5 * 1 * 11 * 13 * 17
## 01001 715 5 * 1 * 11 * 13 * 1
## 01010 935 5 * 1 * 11 * 1 * 17
## 01011 55 5 * 1 * 11 * 1 * 1
## 01100 1105 5 * 1 * 1 * 13 * 17
## 01101 65 5 * 1 * 1 * 13 * 1
## 01110 85 5 * 1 * 1 * 1 * 17
## 01111 5 5 * 1 * 1 * 1 * 1
## 10000 17017 1 * 7 * 11 * 13 * 17
## 10001 1001 1 * 7 * 11 * 13 * 1
## 10010 1309 1 * 7 * 11 * 1 * 17
## 10011 77 1 * 7 * 11 * 1 * 1
## 10100 1547 1 * 7 * 1 * 13 * 17
## 10101 91 1 * 7 * 1 * 13 * 1
## 10110 119 1 * 7 * 1 * 1 * 17
## 10111 7 1 * 7 * 1 * 1 * 1
## 11000 2431 1 * 1 * 11 * 13 * 17
## 11001 143 1 * 1 * 11 * 13 * 1
## 11010 187 1 * 1 * 11 * 1 * 17
## 11011 11 1 * 1 * 11 * 1 * 1
## 11100 221 1 * 1 * 1 * 13 * 17
## 11101 13 1 * 1 * 1 * 13 * 1
## 11110 17 1 * 1 * 1 * 1 * 17
## 11111 1 1 * 1 * 1 * 1 * 1



.

Relevant Pages