solve.py

#!/usr/bin/env python
import math
from collections import defaultdict
import sys
def factors(n):
    result = []
    for i in range(2,n+1): # test all integers between 2 and n
        s = 0
        while n/i == math.floor(n/float(i)): # is n/i an integer?
            n = n/float(i)
            s += 1
        if s > 0:
            for k in range(s):
                result.append(i) # i is a pf s times
            if n == 1:
                fact = defaultdict(int)
                for p in result:
                    fact[p] += 1
                return fact
def possible_divisors(prime_list):
    for prime, count in prime_list.items():
        for sel_count in range(1, count+1):
            yield prime**sel_count

def min_supporters(n):
    n = int(n)
    fact = factors(n)
    cur_min = math.floor(n/2)+1
    cur_divisor = []
    if len(fact) == 1:
        return cur_min, [n]
    for d in possible_divisors(fact):
        if n/d < 3 or d < 3:
            continue
        variant, divisors = min_supporters(n/d)
        if variant * (math.floor(d/2)+1) < cur_min:
            cur_min = variant * (math.floor(d/2)+1)
            cur_divisor = [d] + divisors
    return cur_min, cur_divisor
#print ([x for x in possible_divisors(factors(20000000))])
print (min_supporters(int(sys.argv[1])))