[백준 알고리즘] 1016번: 제곱 ㄴㄴ 수

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

문제

문제
어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력
첫째 줄에 두 정수 min과 max가 주어진다.

출력
첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다.

풀이

이 문제 역시 에라토스테네스의 체를 응용해서 문제를 풀 수 있다. 처음에는 무작정 모든 수에 소수를 곱해서 제곱수가 되지 않는 수를 찾으려고 했는데, 애초에 max의 최대값인 1,000,000,000,000 를 할당하는 것도, 일일히 확인하는 것도 시간이 너무 오래 걸린다. 따라서 min 과 max 를 최대한 활용해서 문제를 풀어야 한다.

문제의 조건에서 max 는 아무리 커도 min + 1,000,000 이라는 조건이 있다. 따라서 이 구간에 있는 숫자들만 확인해주면 아무리 올래걸려도 O(1000000) 만에 처리를 끝낼 수 있다. 제곱 ㄴㄴ 수를 확인해기 위해서 에라토스 테네스의 체를 응용한다.

먼저 bool 타입 배열을 max-min + 1 길이로 만든다. 이 배열의 각 인덱스가 min 부터 max 까지의 숫자를 나타내고, true 는 제곱수로 나누어 떨어지는 수(제곱ㄴㄴ수), false는 제곱ㅇㅇ수를 의미한다. 2부터 max 까지 숫자를 하나씩 올리면서 해당 숫자의 제곱수를 만들고 이 제곱수의 배수 인덱스를 모두 true 로 처리한다. 이때, 인덱스를 정규화해야하기 때문에 min 값을 계속 빼주어서, min 이 0번째, min+1 이 1번째를 나타내도록 한다.

이렇게 하면 배열에서 true가 되어있는 인덱스+min 은 제곱ㅇㅇ수를 의미하게 된다. 이제 false 값을 가진 모든 원소들의 개수를 세어내면 제곱ㄴㄴ수의 개수를 얻게된다.

코드

#include <iostream>
#include <vector>

using namespace std;

int main (){
    long long int min, max;
    cin >> min >> max;

    vector<bool> primes (max-min+1, false);

    for (long long int i = 2 ; i <= max ; i++){
        long long int sqr = i * i;

        if (sqr > max) break;
        long long int start = (min / sqr) * sqr;
        if (start < min) start += sqr;

        for (long long int j = start ; j <= max ; j += (i*i)){
            primes[j - min] = true;
        }
    }

    int answer = 0;
    for (int i = 0 ; i <= max-min; i++){
        if (!primes[i]) answer++;
    }

    cout << answer;
}