AtCoder ABC 106 B - 105 (6Q, 灰色, 200 点)

E8君問題集の第2問

問題へのリンク

問題概要

正の整数 が与えられる。 以上 以下の整数のうち、約数の個数がちょうど 8 個あるものが何個あるかを求めよ。

制約

• 

考えたこと

単純に 1 から までの整数それぞれについて、

• 約数をすべて求めて
• それが 8 個かどうかを調べる

という風にすれば OK。整数 の約数列挙は、以下の記事に解説したような方法で でできる。

qiita.com

しかし今回は制約が緩いため、もっと簡単な方法で かけてしまってもよい。具体的には

• のそれぞれについて、
• が で割り切れるかどうかを調べる

という風にすれば OK。全体の計算量は 。

c++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    int res = 0;
    for (int n = 1; n <= N; n += 2) {
        int cnt = 0;
        for (int i = 1; i <= n; ++i) if (n % i == 0) ++cnt;
        if (cnt == 8) ++res;
    }
    cout << res << endl;
}

python

N = int(input())
res = 0
for n in range(1, N+1, 2):
    cnt = 0
    for i in range(1, n+1):
        if n % i == 0:
            cnt += 1
    if cnt == 8:
        res += 1
print(res)