ABC106-B個人的なメモ（解答）

ABC106-B

https://atcoder.jp/contests/abc106/tasks/abc106_b

約数列挙の高速化

高速な素数判定法の応用

for (int i = 1; i * i <= arg_i; i++) {
		if (arg_i % i != 0)continue;
		cnt++;
		if (i != arg_i % i)cnt++;
}

↑E869120さんの本で学んだ

#include<iostream>
using namespace std;

bool isYes(int arg_i) {
	
	int cnt = 0;
	for (int i = 1; i * i <= arg_i; i++) {
		if (arg_i % i != 0)continue;
		cnt++;
		if (i != arg_i % i)cnt++;
	}
	if (cnt == 8)return true;
	else return false;
}

int main() {
	
	int N;
	cin >> N;
	bool canAdd;
	int cnt = 0;

	for (int i = 1; i <= N; i++) {
		if (i % 2 == 0)continue;
		canAdd = isYes(i);
		if (canAdd)cnt++;
	}
	cout << cnt << endl;
	return 0;
}