Day 002-Q3 | 約数列挙

問題

正の整数 N が与えられる。N の全ての約数を昇順で出力せよ。

入力形式

制約

$1 \le N \le 10^{12}$

入出力例

入力例 1

出力例 1

1 2 3 4 6 12

入力例 2

出力例 2

1 2 3 4 6 9 12 18 36

ヒント (段階的開示)

ヒント1: 方向性

1 から N まで全部試すと O(N)、N=10^12 では遅すぎる。

ヒント2: アプローチ

i が約数なら N/i も約数。1〜√N まで i を試し、N % i == 0 なら i と N//i の両方を記録 → O(√N)。

ヒント3: 誘導

import math

divisors = []
for i in range(1, int(math.sqrt(N)) + 1):
    if N % i == 0:
        divisors.append(i)
        if i != N // i:
            divisors.append(N // i)
divisors.sort()

模範解答 (Python)

import math

N = int(input())

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

divisors.sort()
print(*divisors)

Step-by-Step 解説

1√N まで試す理由
約数はペアで現れる。N=12 なら 1×12, 2×6, 3×4。小さい方（≤ √N）を見つければ大きい方（N//i）も同時に求まる。

2重複を避ける
N が完全平方数（例: N=9, i=3）のとき N//i=3 で同じ数を2回追加してしまう。if i != N // i で防ぐ。

3ソートして出力
print(*divisors) でスペース区切り出力。

計算量

時間: $O(\sqrt{N})$ — N=10^12 で約 10^6 回
空間: $O(\text{約数の個数})$

よくあるミス

ミス	原因	正しい書き方
`range(1, N+1)`	O(N) でTLE	`range(1, int(sqrt(N))+1)`
重複チェック忘れ	完全平方数で同じ約数2つ	`if i != N // i`
sqrt の浮動小数誤差	sqrt(4)=1.999...	+1 で安全マージン

Day 002-Q3 — 約数列挙

問題