問題文

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

N = 10000

# 素因数分解
def f(n):
    res = defaultdict(int)
    d = 2
    while d * d <= n:
        while n % d == 0:
            res[d] += 1
            n /= d
        d += 1
    if n > 1:
        res[n] += 1
    return res

for i in xrange(1, N+1):
    a = f(i)
    y = i
    for k, v in a.items():
        while v >= 2:
            y /= (k * k)
            v -= 2
    x = int((i / y) ** .5)
    res = '√{0} -> '.format(i)
    if y == 1:
        print (res + '{0}').format(x)
    elif x == 1:
        print (res + '√{0}').format(y)
    else:
        print (res + '{0}√{1}').format(x, y)

# 初心者向け

import math

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

print "√" + str(1) + " -> " + str(1)
for r in range(2, 10000 + 1):
	 u = []
	 if r in t:
		 print "√" + str(r) + " -> " + str(int(math.sqrt(r)))
	 else:
		 x = 1
		 for w in t:
			 if r % w == 0:
				 r /= w
				 x *= (int(math.sqrt(w)))
		 if x > 1:
			 print "√" + str(r*(x**2)) + " -> " + str(x) + "√" +  str(r)
		 else:
			 print "√" + str(r) + " -> " + "√" + str(r)