제곱 ㄴㄴ수

에라토스테네스의 체 원리를 이용한 간단한 문제이다.

그냥 min부터 max까지 돌면서 sqrt(max)보다 작은 값들의 제곱수로 나눠 떨어지는 수들을 하나씩 제외하면 된다.

이미 제외한 수들을 중복해서 제거하지 않기 위해 check 배열을 만드는데 이 배열로 체크할 때 인덱스를 min으로 빼야 배열 크기를 줄일 수 있다. (안 빼면 인덱스가 최대 max까지 늘어나야 해서 불가능)

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
long long minv, maxv;
int check[1000004];
int main()
{
    scanf("%lld %lld",&minv,&maxv);
    int arrange = int(sqrt(maxv));
    long long ans = maxv-minv+1;
    for(long long i=2;i<=arrange;i++)
    {
        long long x = i*i;
        long long st = minv/x;
        long long comp;
        if(minv<=st*x) comp = st*x;
        else comp = (st+1)*x;
        while(maxv>=comp)
        {
            if(check[comp-minv]==0){
                ans--;
                check[comp-minv]=1;
            }
            comp+=x;
        }
    }
    printf("%lld",ans);
}

나머진 그냥 구현만 하면 되는 엄청나게 간단한 문제이다.