AtCoder ABC 106 B – 105 Python解説

2021年12月3日

105

105 という数は, 非常に特殊な性質を持つ – 奇数なのに, 約数が 8 個もある.
さて, 1 以上 N 以下の奇数のうち, 正の約数を ちょうど8 個持つようなものの個数を求めよ.

AtCoder Beginner Contest 「105」

今回の問題ではNの範囲が1以上200以下と制約が緩いため、2重ループでN以下の奇数の約数をすべて調べていこうと思います。

n = int(input())

ans = 0

for i in range(1, n + 1, 2):
    cnt = 0
    for j in range(1, n + 1):
        if i % j == 0:
            cnt += 1
    if cnt == 8:
        ans += 1
        
print(ans)

内側のループのif i % j == 0で約数になるか調べています。約数だったらcnt+1して約数が8だったらans+1しています。