TopCoder SRM 575 - DIV 1 Level 1

http://community.topcoder.com/stat?c=problem_statement&pm=12496&rd=15495

The solution for the smaller problem:


def myfunc(n):
    f = [0] *(n+1)
    for i in range(2,n+1):
        for j in range(2,i):
            if(i%j==0 and f[i-j]==0):
                f[i] =1
    print [ (i,f[i]) for i in range(0,len(f))]

The solution for the bigger problem involves getting a pattern from the above solution.
http://apps.topcoder.com/wiki/display/tc/SRM+575

Divisor counting

Count the number of divisors of a number given its prime factors in the form:

If a number n look like this:

n = a^p * b^q * c^r * d^s * e^t * f^u ... ,

where a,b, c and so on are its prime factors

then the number of divisors of n = (p+1)*(q+1)*(r+1)*...

This is because we can choose any number of a's from 0 to p, which gives us (p+1) choices, and so on.

http://mathforum.org/library/drmath/view/55741.html