백준 1016 (제곱 ㄴㄴ 수) / C++

문제 링크 : https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

> 풀이

에스토스테네스의 체의 원리를 응용하는 문제입니다. 에스토스테네스의 체가 어떤 원리로 작동하는지를 알고 있다면 쉽게 접근 할 수 있을겁니다.

 

max와 min 사이에 있는 수가 최대 1000000개 이므로 결과를 저장할 배열을 만들어 주고, max 보다 작은 제곱수들에 대해 (4, 9, 16 ...) 배수를 늘려가며 해당 범위에 들어가는지 체크해 주시면 됩니다.

#include <cstdio>

long long number[1000001];

int main(void) {
        long long min, max;
        int cnt = 0;

        scanf("%lld %lld", &min, &max);

        for (long long i = 2; i * i <= max; i++) {
                long long n = min / (i * i);
                
                if (min % (i * i)) n++;

                while (n * i * i <= max) {		//n*i*i는 min보다 크거나 같은 i의 제곱수의 배수
                        number[n * i * i - min] = 1;
                        n++;
                }
        }

        for (int i = 0; i <= max - min; i++) {
                if (number[i] == 0) cnt++;
        }

        printf("%d", cnt);
        return 0;
}

(개발 환경 : vs code)