Project Euler problem 500

500.py

# https://projecteuler.net/problem=500 Project Euler problem 500
"""The number of divisors of 120 is 16.
In fact 120 is the smallest number having 16 divisors.

Find the smallest number with 2**500500 divisors.
Give your answer modulo 500500507."""

from codejamhelpers import primes
import heapq

def solve(k, modulus=None):
    """Calculate the smallest number with 2**k divisors."""
    n = 1
    
    costs = primes[:k] # more than necessary

    for i in range(k):
        cost = heapq.heappop(costs)
        heapq.heappush(costs, cost**2)
        n *= cost
        if modulus:
            n %= modulus

    return n

assert solve(4) == 120

if __name__ == "__main__":
    print(solve(500500, 500500507))