唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Project Euler 124

エラトステネスのふるい的に素因数分解、積を求めてソート。

def rad(MAX):
  rad = [1] * MAX
  
  i = 2
  while MAX + 1 > i:
    if rad[i - 1] == 1:
      rad[i - 1] *= i
      temp = i * 2
      while temp < MAX + 1:
        rad[temp - 1] *= i
        temp += i
    
    if i == 2:
      i += 1
    else:
      i += 2
  
  return rad

N = 100000

rad_i = zip(rad(N), xrange(1, N + 1))
rad_i.sort()

print rad_i[9999][1]