The number of divisors of 120 is 16. In fact 120 is the smallest number having 16 divisors. Find the smallest number with
divisors. Give your answer modulo 500500507.
The question is to minimize
such that
.
It is clear that each
has to be in the form
of
with
.
Each time we increase
by 1, the product increases by
Therefore we can use priority queue to store down next product increment.
from simplemath import sieve
from heapq import heappush, heappop
def p500(N=500500):
M = 500500507
p = sieve(10000000)
assert len(p) > N
h = []
for i in range(N):
heappush(h, (p[i], p[i], 1))
n = 0
ans = 1
while n < N:
num, pi, ki = heappop(h)
n += 1
ans *= num
ans %= M
heappush(h, (pi ** (2 ** ki), pi, ki + 1))
return ans35407281