4, 9, 16… 같은 제곱수으로 나눠지지 않는 주어진 수 사이의 숫자 개수를 구하는 문제입니다.
주어지는 min의 최대값이 1,000,000,000,000라서 브루트포스하게 못 할 것 같지만 min과 max 사이의 차이가 최대 1,000,000이기 때문에 충분히 브루트포스로 가능합니다. 에라토스테네스의 체를 살짝 변형해서 for문을 만들면 되는 문제입니다.
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
int nono[10000111];
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll min, max; cin >> min >> max;
ll ans = max - min + 1;
for(ll i = 2; i * i <= max; i++){
ll s = min / (i * i);
if(s * i * i < min){
s += 1;
}
for(ll j = s * i * i; j <= max; j += i * i ){
if(nono[j - min] == 0){
nono[j - min] = 1;
ans--;
}
}
}
cout << ans;
}