AtCoder Beginner Contest 106 B - 105を自分的にまとめる（Python）

今回はB - 105をまとめようと思います。

リンクはこちらから

①考え方

この問題は、1 ~ Nまで1つずつ約数の個数を調べていき、その中で約数の個数が8個となりそしてその数が奇数となる数の個数を求めるプログラムを書くことでACになります。
全探索を使いましょう。

1. 約数の個数を調べる

まず約数の個数を調べるコードを書いていきましょう。
まず配列aを用意します。
その次に、1 <= i <= nまで探索します。
その際に、n%i = 0のiをaに追加していきます。
そして、setをとり重複がないようにしてあげます。
setをとった後のaのサイズが約数の個数と一致します。
以上で約数の個数を求めるプログラムができました。

実装例は以下の通りです

実装例1

def divisor(n):
    a = []
    for i in range(1,n+1):
        if n % i == 0:
            a.append(i)
    a = set(a)
    return len(a)

関数定義しなくてもできますが、個人的にこの形が好きなのでこのようにしました。
※約数なのでそれにちなんだ名前にしました。

2. 1 <= i <= nまで探索

1 ~ N までそれぞれの数に対して約数の個数を求めていきたいので
1 <= i <= nまで探索してあげます。その際に、
約数の個数が8個かつその数が奇数となる数ケースを数えていきます。

実装例は以下の通りです

実装例2

ans = 0
for i in range(1,n+1):
    if divisor(i) == 8 and i % 2 == 1:
        ans += 1

提出したコード

solution

def divisor(n):
    a = []
    for i in range(1,n+1):
        if n % i == 0:
            a.append(i)
    a = set(a)
    return len(a)

n = int(input())
ans = 0
for i in range(1,n+1):
    if divisor(i) == 8 and i % 2 == 1:
        ans += 1
print(ans)

まとめ

この問題では全探索を使う問題でした。付け加えていうならば、約数とはどんな数なのかをおさえておくことも必要ですかね。最後に、参考文献に問題のリンクと自分がよく閲覧している記事を紹介しておきます。

参考文献