[BOJ] 백준 1016번: 제곱ㄴㄴ수

제곱으로 나누어떨어지지 않는 수를 찾기 위하여 1부터 _max의 제곱근 까지의 소수를 찾아 리스트에 저장한 후

_min과 _max의 범위가 최대 100만 차이임을 이용하여 찾은 소수 제곱에 대한 배수를 채로 걸러 전체 수에서 뺌

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
#include <math.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
ll _min, _max;
bool s[1000001] = { 0, };
bool ans[1000001] = { 0 , };
vector<ll> v;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	cin >> _min >> _max;
	ll r = sqrt(_max);
	ll re = _max - r;
	s[1] = 1;
	for (ll i = 2; i <= r; i++) {
		if (!s[i]) {
			v.push_back(i*i);
			for (ll j = i + i; j <= r; j += i) {
				s[j] = 1;
			}
		}
	}
	for (auto pr : v) {
		ll s;
		ll moc = _min / pr;
		ll re = _min % pr;
		if (re) {
			moc += 1;
		}
		s = pr * moc;
		for (ll i = s; i <= _max; i += pr) {
			ans[i - _min] = true;
		}
		
	}
	ll cnt = 0;
	for (ll i = _min; i <= _max; i++) {
		if (!ans[i - _min]) {
			cnt += 1;
		}
	}
	cout << cnt;
}