import math def factor(b): facts = [] i = 2 while i <= math.sqrt(b): if b%i == 0: facts += [i,b/i] i += 1 return facts def egypt(a,b): fraction = [] F = factor(b) G = factor(a) i = 0 while i < len(G): if G[i] in F: b = b/G[i] a = a/G[i] F = factor(b) G = factor(a) i = 0 i += 1 i = len(F)-1 if i <= 0: if b/a < 2: mult = 2 else: mult = (int(b/a)+1) a = mult*a b = mult*b F = factor(b) i = len(F)-1 #print a,b,F temp = [] temp2 = 0 while a > 1: temp += [a] while i >= 0: #print a,F[i] if a >= F[i] and not b/F[i] in fraction: a = a-F[i] temp2 = F[i] fraction += [b/F[i]] i-=1 if a <= 1 or (b%a == 0 and b/a not in fraction): if a > 1: fraction += [b/a] a = 0 break i+= 1 while i < len(F) and F[i] <= a: i += 1 if i == len(F) or F[i]/a < 2: mult = 2 while a*mult in temp or mult == temp2: mult +=1 else: mult = int(F[i]/a)+1 if mult == temp2: mult += 1 a *= mult b *= mult F = factor(b) i = len(F)-1 #print fraction,b #raw_input() if a == 1: fraction += [b] print fraction egypt(25,37)