はじめに
この記事は 共通テスト手順記述標準言語 (DNCL) Advent Calendar 2025 の９日目の記事です。
共通テストで使われるDNCLを使って約数を求めるプログラムを作ります。
約数を求める
約数はある数を割り切れる数のことなので、例えば９６の約数を求めたいときは１から９６までのすべての数で９６を割って、割り切れたものを約数として採用すればOKです。
kazu ← 96
i を1から kazu まで1ずつ増やしながら、
| もし kazu % i == 0 ならば
| | i を表示する
| を実行する
を実行する
しかし↑のコードではkazuが大きくなると試す数も多くなるので約数を求め終わるまでに時間がかかります。もう少し速く求めるにはどうすればいいでしょうか。
例えば、９６の約数である４は９６÷４=２４なので２４とセットです。このことを利用すると、iは１から９６ではなく１から√96まででいいことがわかります。
kazu ← 96
i ← 1
i * i <= kazu の間、
| もし kazu % i == 0 ならば
| | j ← kazu ÷ i
| | もし i != j ならば
| | | j を表示する
| | を実行する
| | i を表示する
| を実行する
| i ← i + 1
を繰り返す
このようにiを１から√96までにすれば計算量がO(√N)になるので計算回数が大幅に減ります。このやり方なら、たとえ100000000（１億）の約数を求めるときも１から100000000までの１億個ではなく、1から10000（１万）までの１万個を調べるだけで済みます