7K12 blog

猫でも分かるアルゴリズム解説

AOJ NTL_1_A Prime Factorize

f:id:tkr987:20200723222315p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4693828

f:id:tkr987:20200723225619p:plain

Nを2から順番に割っていって因数を求める。このとき割る数は \sqrt Nまでで良い。もし、 \sqrt N以上の数字aで割れるとすると商bは \sqrt N以下になる。もし、aとbが両方 \sqrt N以上だとN < abとなるため矛盾する。