- プログラミングのお題スレ Part18
600 ：253[sage]：2020/09/28(月) 22:51:28.57 ID:mT2w1+AU - >>509 Python3, >>576を参考に計算量を√nに減らした解法
import math
for n in [81, 87, 91, 13]:
s = math.sqrt(n)
f = n
for i in reversed(range(2, 1 + math.floor(s))):
q, m = divmod(n, i)
if m == 0: f = q; break
print(n, '=>', f)
実行結果
~ $ python 18_509_99_rootn.py
81 => 9
87 => 29
91 => 13
13 => 13
もっとスマートな解法を考えていると双曲線を意識した解法を意識してしまうが、
簡単には解けない数学の問題に突き当たると思う
|