Created
November 16, 2017 09:20
-
-
Save ngo/6ff1d9175937b77c3e093086f0cfffc5 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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]))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment