백준 1016 제곱 ㄴㄴ수

문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 제곱ㄴㄴ수의 개수를 출력한다.

 

풀이

에라토스테네스의 체를 이용해서 구한다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>

using namespace std;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	long long min, max;
	cin >> min >> max;

	long long ans = max - min + 1; 

	//use the sieve of Eratosthenes
	vector<bool> sieve(max - min + 1, false);

	for (long long i = 2; i * i <= max; i++) {
		long long sNum = min / (i * i);
		if (min % (i * i) != 0)
			sNum += 1;

		while (sNum * (i * i) <= max) {
			if (sieve[sNum * (i * i) - min] == false) {
				sieve[sNum * (i * i) - min] = true;
				ans -= 1;
			}
			sNum += 1;
		}
	}

	cout << ans;
	return 0;
};