けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 106 B - 105 (200 点)

E8君問題集の第2問

問題へのリンク

問題概要

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

制約

  •  1 \le N \le 200

考えたこと

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

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

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

qiita.com

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

  •  i = 1, 2, \dots, n のそれぞれについて、
  •  n i で割り切れるかどうかを調べる

という風にすれば OK。全体の計算量は  O(N^{2})

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)