【競プロ】過去問精選100問「AtCoder Beginner Contest 106 B - 105」解法
Free-PhotosによるPixabayからの画像

はじめに

このシリーズではレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編:目指せ水色コーダー!】でまとめられている100問をPythonで解いています。

問題

AtCoder Beginner Contest 106 B - 105

ポイント

この問題は全探索を用いて解くことができます。

ある数Xが与えられた時に1とXはXの約数になることは自明なので、ここでは1以上N以下の奇数Xについて、

1以外、X未満の約数の数を調べます。

奇数の約数は奇数になることを利用してループ回数を減らします。

コード

def main():
    N = int(input())
    result = []

    for i in range(1, N + 1, 2):  # 1以上N以下の奇数を全探索
        count = 0
        for j in range(3, i, 2):  # 奇数の約数は奇数になる 1と問題の奇数自身は自明なので調べない
            if i % j == 0:
                count += 1
        if count == 6:  # 1と問題の奇数自身以外に約数がちょうど6つあれば条件を満たす。
            result.append(i)

    print(len(result))


if __name__ == '__main__':
    main()
おすすめの記事