Problem 429

Comments

This one felt relatively easy to me. I needed to find the prime factorization of n! and then find all divisors that “suck up” all of a single prime factor. In other words, if the prime factorization includes 5^13 then the divisor must either have all 5^13 or none 5^0.

Coming up with these divisors was relatively easy and just required a simple loop through the prime factors. The more difficult part was efficiently finding the prime factorization of such a huge number.

I initially used my normal primes_iterator for this which included going through all odd numbers below a possible prime and seeing if it divides evenly. Once I’d already gotten the answer, I wanted to see how much faster the Sieve of Eratosthenes was. I implemented it pretty quickly and wow did it speed things up! Went from taking about 4 minutes to about 8 seconds!

Code

modulo = 1000000009

def primes_iterator(top):
    primes = [True] * (top + 1)
    for p, is_prime in enumerate(primes):
        if not is_prime or p < 2:
            continue
        yield p
        num = p + p
        while num <= top:
            primes[num] = False
            num += p

def solve(n):
    total = 1
    for p in primes_iterator(n):
        exp, div = 0, p
        while div <= n:
            exp += n // div
            div *= p
        total += total * pow(p, 2 * exp, modulo) % modulo
    return total % modulo

if __name__ == '__main__':
    import sys
    n = int(sys.argv[1])
    print(solve(n))