lördagsnöje

gistfile1.py

#!/usr/bin/env python

from operator import mul
import sys

# from problem10.py
def sieve_primes(num):

    numbers = [True] * num;

    for n in xrange(2, num + 1):
        # Replace all True elements with False elements if they are
        # multiplies of a number in the range.
        #
        # len will be called 1999999 times for n = 2 000 000, not very
        # optimized.
        l = len(numbers[n*n::n])
        numbers[n*n::n] = l * [False]

    return numbers

# from problem05.py
def factorize(n):
    """
    Naive and slow factorization.
    """
    factors = [1]

    if n <= 0: return []
    if n == 1: return factors

    for p in primes:
        if n % p == 0:
            factors.append(p)

    prod = reduce(mul, factors)

    if n != prod:
        factors.extend(factorize(n / prod))

    factors.remove(1)

    return sorted(factors)

def divisors(n):
    # n = a^n + b^m + ... + c^q 
    # divisors = (n + 1) * (m + 1) + (q + 1)    

    # 2, 2, 5, 5, 5, 7, 11, 13
    # =>
    # get exponent of primes
    # 2 3 1 1 1 
    # =>
    # 3 4 2 2 2
    # return reduce(mul, prime_exponents)

    f = factorize(n)

    i = 0
    exps = []

    while i < len(f):
        c = f.count(f[i])
        i = i + c
        exps.append(c)

    exps = [n + 1 for n in exps]

    return reduce(mul, exps)

i = 1
divs = 500

# get all the primes < n
n = 10000000
p = sieve_primes(n)
primes = [n for n in range(2, n) if p[n] == True]

while(True):
    n = sum(range(1, i + 1))
    d = divisors(n)

    print str(n) + " : " + str(d)
    
    if d > divs:
        print n
        break

    i += 1