#!/usr/bin/env pythonimport sysdef getFactors(number): if number < 2: return [] factors, end = [], int(number**.5) for i in range(2, end+1): factor = i while number % factor == 0: factors.append(factor) number /= factor if number > end: factors.append(number) return sorted(factors)def reduceFraction(num, den): num = getFactors(num) den = getFactors(den) for i,f in enumerate(num): if f in den: num[i] = 1; den.remove(f) if len(num) == 0: num = 1 else: num = reduce(lambda x,y: x*y, num) if len(den) == 0: den = 1 else: den = reduce(lambda x,y: x*y, den) return num, denif len(sys.argv) > 1: end = int(sys.argv[1])else: end = int(1e6)fractions = set([])for d in range(1,end+1): for n in range(1,d): fractions.add( reduceFraction(n,d) )print "%d reduced proper fractions for d = %d" % (len(fractions), end)# for frac in fractions:# print "%d/%d" % (frac[0], frac[1])