[Gold / 1016] 제곱 ㄴㄴ 수

문제 링크

---

🔷 분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

✒️ 문제 설명

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

⬅️ 입력

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

➡️ 출력

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

💻 코드 (C++)

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	long long min, max;
	cin >> min >> max;
	vector<bool> check(max - min + 1, 0);
	
	// 에라토스테네스 체 변형
	for(long long i = 2; i * i <= max; i++) {
		long long pow = i * i;
		long long st_index = min / pow;
		if(min % pow != 0) st_index++; // 나머지 있으면 +1
		for(long long j = st_index; pow * j <= max; j++) { // 제곱수 true로 바꾸기
			check[(int)((j * pow) - min)] = true;
		}
	}
	
	int ans = 0;
	for(int i = 0; i <= max-min; i++) {
		if(!check[i]) ans++;
	}
	cout << ans;
	return 0;
}