Skip to content

Instantly share code, notes, and snippets.

@hickford hickford/500.py
Created Jul 7, 2015

Embed
What would you like to do?
Project Euler problem 500
# 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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.