はじめに

こちらの記事をご覧頂きありがとうございます！！
2020年6月よりプログラミングデビューしたなかぞんです！

毎日、AtCorderのA-D問題を最低5問解くことを日課としています。

私の記事では、プログラミング初心者の目線で、
日々の日課を通じて発見した学びや苦労した事、
嬉しかった事などを発信しようと思います。

同じ初心者の方々に学びのある記事になるよう努めて参ります！
上級者の方は温かい目で見守ると共に、
プラスの知恵やアドバイスを是非ともお待ちしてます！

それでは、本日の内容に参ります！！

問題

本日の学びの元となった問題はこちら

C - Walk on Multiplication Table
https://atcoder.jp/contests/abc144/tasks/abc144_c

例題のN=10で考えてみると、iとjの候補は (1, 10) (2, 5)の２つ。
N = i * j を満たすiとjの組み合わせでi + jが最小のものを考えればよいですね。
じゃあ「約数を取得しよう！」と考えたところで、
「あれ？どうすればいいんだっけ」状態に陥る。。。笑

自然数Ｎの約数はこうやって取得する！！

Nが最大10**12なのでfor文で1から全探索するのは
時間がかかりすぎるので工夫が必要です。

N = int(input())
divisors = []
for i in range(1, int(N**0.5)+1):
    if N % i == 0:
        divisors.append(i)
        if i != N // i:
            divisors.append(N//i)

divisors.sort()

このように√Ｎ（約数の折り返し地点）まで探索すれば
全ての約数は取得できるということがポイントですね。

最後に

こういうアルゴリズム素で気づける人になりたい。
てか気づけるやつすげえな