import math
for i in range(2, 10000000): # 3.652s / 10 000 000
    sqrt = math.sqrt(i)
    nq = sqrt / math.pow(i, 1)
    if nq % sqrt == 0: continue