問題文

解答例1

#coding:utf-8

import math, fractions

t = []
for i in range(int(math.sqrt(10000)), 1, -1):
	 t.append(i**2)

dic = {}
for r in range(2, 10000 + 1):
	 u = [str(r)]
	 if r in t:
			 dic.update(dict.fromkeys(u, [int(math.sqrt(r)), 1]))
	 else:
		 x = 1
		 for w in t:
			 if r % w == 0:
				 r /= w
				 x *= (int(math.sqrt(w)))
		 if x > 1:
			 dic.update(dict.fromkeys(u, [int(x), r]))
		 else:
			 dic.update(dict.fromkeys(u, [1, r]))

for a in range(1, 101):
	 for b in range(2, 101):  
		 c = a * b   
		 z = dic[str(c)]
		 if z[0] == 1:
			 print "√" + str(a) + "/" + "√" + str(b) + " -> " + "√" + str(z[1]) + "/" + str(b)
		 elif z[1] == 1:
			 print  "√" + str(a) + "/" + "√" + str(b) + " -> " + str(fractions.Fraction(z[0], b))
		 else:
			 if fractions.Fraction(z[0], b) == 1:
				 print  "√" + str(a) + "/" + "√" + str(b) + " -> " + "√" + str(z[1])
			 else:
				 print  "√" + str(a) + "/" + "√" + str(b) + " -> " + "(" + str((fractions.Fraction(z[0], b))) + ")" + "*" + "√" + str(z[1])

解答例2

# -*- coding: utf-8 -*-
from fractions import gcd
from collections import defaultdict

N = 100

# √nの有理化
# 答え: x√y
def f1(n):
    p = n
    d = 2
    dic = defaultdict(int)
    while d * d <= p:
        while p % d == 0:
            dic[d] += 1
            p /= d
        d += 1
    if p > 1:
        dic[p] += 1
    y = n
    for k, v in dic.items():
        while v >= 2:
            y /= (k * k)
            v -= 2
    x = int( (n/y) ** .5 )
    return x, y

cache = {}

def f2(n):
    if not n in cache:
        cache[n] = f1(n)
    return cache[n]

for a in xrange(1, N+1):
    for b in xrange(2, N+1):
        # √a      xa√ya
        # --- = ----------
        # √b      xb√yb
        xa, ya = f2(a)
        xb, yb = f2(b)
        if yb > 1:
            ya *= yb
            xb *= yb
#            yb = 1 #になる
            xxa, yya = f2(ya)
            xa *= xxa
            ya = yya
        g = gcd(xa, xb)
        xa /= g
        xb /= g
        left = '√{0}/√{1} -> '.format(a, b)
        # 分母が1
        if xb == 1:
            if ya == 1:
                print(left + '{0}'.format(xa))
            elif xa == 1:
                print(left + '√{0}'.format(ya))
            else:
                print(left + '{0}√{1}'.format(xa, ya))
        # 分母がある
        else:
            if ya == 1:
                print(left + '{0}/{1}'.format(xa, xb))
            elif xa == 1:
                print(left + '√{0}/{1}'.format(ya, xb))
            else:
                print(left + '{0}√{1}/{2}'.format(xa, ya, xb))