[PS] BOJ 1016 제곱ㄴㄴ수

https://www.acmicpc.net/problem/1016

에라스토테네스의 체 문제이다.

제곱ㄴㄴ수를 계산하는 것은 매우 오래 걸리므로 제곱ㅇㅇ수를 구하여 나머지를 세면 간단하다.

sqrt(max) 이하의 숫자들의 제곱의 배수들을 모두 체크하면 된다.

유의할 점은 에라스토테네스의 체를 사용할 때 0부터 시작하게 만들어야 한다는 점이다.

min값을 빼주어 0부터 시작하게 하면 1,000,000이내로 계산이 가능하다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using lld = long long;
int main() {
	const int N = 1000001;
	lld minv, maxv;
	cin >> minv >> maxv;
	vector<bool> bloom(N, false);
	for (lld i = 2; i*i <= maxv; i++) {
		lld k = minv / (i*i);
		if (k*i*i != minv)k++;
		if (k*i*i > maxv && bloom[k*i*i - minv])continue;
		while (k*i*i <= maxv) {
			bloom[k*i*i - minv] = true;
			k++;
		}
	}
	int A=std::count(bloom.begin(), bloom.begin()+(maxv-minv+1), false);
	cout << A << endl;
	return 0;
}