1016번: 제곱 ㄴㄴ 수

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

#include<stdio.h>
typedef long long ll;
const int N = 1000000;
ll s, e;
bool ck[N + 1], sck[N + 1];
int main() {
    scanf("%lld %lld", &s, &e);
    int res = e - s + 1;
    for (ll i = 2; i <= N; i++) {
        if (sck[i]) continue;
        for (ll j = ((s - 1) / (i*i) + 1)*i*i; j <= e; j += i*i) {
            if (!ck[j - s]) {
                res--;
                ck[j - s] = true;
            }
        }
        for (int j = i; j <= N; j += i)
            sck[j] = true;
    }
    printf("%d", res);
    return 0;
}