はじめに
このシリーズではレッドコーダーが教える、競プロ・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()