백준 1016 제곱 ㄴㄴ 수

http://www.acmicpc.net/problem/1016 

1016번: 제곱 ㄴㄴ 수

에라토스테네스의 체를 사용하지않을경우 제곱수들의 최소공배수들로 세기 매우 복잡해지므로 에라토스테네스의 체를 이용하는 문제였습니다.

a<=x<=b 의 범위에서 a와 b의수는 매우크지만 b-a는 최대 100만이므로 범위의 수를 이용해서 푸는 문제인것을 알 수 있습니다. 가장작은 제곱수는 4이므로 100만범위안에서 제곱수들을 bool 배열에 체크하면서 나중에 체에 걸린 개수를 세면 됩니다.

#include <stdio.h>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
bool chk[1000001];
int main(){
    fast_io();
    long long a,b;
    cin>>a>>b;
    int ans=0;
    for(long long x=2;x*x<=b;x++){
        for(long long k=a-(a%(x*x));k<=b;k+=(x*x)){
            if(k<a) continue;
            chk[k-a]=true;
        }
    }
    for(int x=0;x<=b-a;x++){
        if(!chk[x]) ans++;
    }
    cout<<ans;
}