[c++][백준 1016] 제곱 ㄴㄴ 수

백준 1016번: 제곱 ㄴㄴ 수 [Gold 1]
https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

문제 풀이

• 이 문제는 소수를 구할 때 사용하는 에라토스테네스의 체의 원리를 사용해 풀었다. 
• 2부터 시작해서 min ~ max 사이에 있는 제곱수를 체크해야 하는데, 이때 최대 10^12까지 입력이 들어오기 때문에 제곱수를 그대로 arr의 index로 사용하게 되면 메모리가 감당하지 못한다. (arr[10^12]로 선언해야 하기 때문,,,)
• 문제에서 다른 제한으로 min과 max의 차이가 최대 10^6이라고 했기 때문에, arr[10^6]짜리를 선언하여 (제곱수 - min)으로 index를 사용했다.

코드

#include <cstdio>

using namespace std;

int arr[1000010];

int main() {
    long long mn, mx;
    scanf("%lld %lld", &mn, &mx);

    for(long long i=2; i*i<=mx; ++i) {
        long long square = i * i;

        long long quotient = mn / square;
        if(quotient*square < mn) quotient++;

        while(quotient*square <= mx) {
            arr[quotient*square - mn] = 1;
            quotient++;
        }
    }

    int answer = 0;
    for(int i=0; i<=mx-mn; ++i) {
        if(!arr[i]) answer++;
    }

    printf("%d", answer);

    return 0;
}

 

실행 결과