<백준> 1016

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

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

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

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

	vector<bool> v(max - min + 1);

	for (long i = 2; i * i <= max; i++)
	{
		long pow = i * i;
		long start = min / pow;

		if (min % pow != 0)
			start++;
		for (long j = start; pow * j <= max; j++)
		{
			v[(int)((j * pow) - min)] = true;
		}
	}

	int count = 0;

	for (int i = 0; i <= max - min; i++)
	{
		if (!v[i])
			count++;
	}
	cout << count;
}