제곱ㄴㄴ수(BOJ 1016)

1016.cpp

#include<iostream>
#include<vector>
 
using namespace std;
bool f[5555555];
int main()
{
    vector<long long> v;
    long long a,b,len,ans=0;
 
    cin>>a>>b;
    for(long long i=2;i*i<=b;i++) v.push_back(i*i);
 
    len=v.size();
    for(int i=0;i<len; i++)
    {
        for(long long j=(a/v[i])*v[i];j<=b;j+=v[i])
        {
            if(j-a>=0 && !f[j-a])
                f[j-a]=1,ans++;
        }
    }
    cout<<b-a-ans+1;
}