[1016] 제곱 ㄴㄴ 수

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

1016 - 제곱 ㄴㄴ 수

본문

어떤 정수 $X$가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

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

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

시간 제한	메모리 제한
2sec	512MB

• $1 \leq \text{min} \leq 1000000000000$ (${10}^{12}$)
• $\text{min} \leq \text{max} \leq \text{min} + 1000000$

---

풀이

C로 문제를 푸는 내 입장에서는 입력만 보면 숨이 막히는 문제이다. 입력되는 숫자 단위가 최대 1조이다. 다행히 시작점이 몇이든 탐색해야하는 값의 범위는 100만까지인 점이 다행이라고 할 수 있다.

먼저 문제에서 주어지는 조건에서, 정수의 제곱수들로 나누어 떨어지지 않는 수를 찾아야 한다. 제곱수는 $2^2=4$부터 $3^2=9, 4^2=16, 5^2=25, \cdots$ 순으로 계속해서 존재한다. 당연하게도, 이 제곱수는 $\text{max}$까지 돌려봐야할 것이다.

그럼 특정 수가 제곱ㄴㄴ수인지 어떻게 기록할 수 있을까? 이 방법으로 에라토스테네스의 체 방법에서 사용했던 배열 저장 방법을 사용하려한다. 기존의 에라토스테네스의 체 방법에서는 소수로 나누어 떨어지는 수를 모두 제거하는 과정을 거쳤지만, 이 문제에서는 제곱수로 나누어 떨어지는 수를 모두 제거하는 것으로 변형해서 사용한다. 배열이 나타내는 값의 범위는 min부터 max까지로 나타낸다. 배열의 시작지점이 min, 끝지점이 max라고 생각하는 것이다.

• 참고 알고리즘 : 에라토스테네스의 체

코드

사용 언어 : C

최종 수정일 : 2023 / 1 / 10

#include <stdio.h>

typedef long long ll;
typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX (int)(1e6 + 1)
bool squareInt[MAX_IDX];
ll min, max;

ll getSquareRoot(ll n) {
    ll x = 1;
    while (x * x <= n) {
        ++x;
    }
    return --x;
}

int main() {
    scanf("%lld %lld", &min, &max);

    // get square root of max
    ll sqrtMax = getSquareRoot(max);

    // Sieve of Eratosthenes
    for (ll i = 2; i <= sqrtMax; ++i) {
        ll square = i * i;

        // get start point
        ll startPoint = (min / square) * square;
        if (startPoint < min) {
            startPoint += square;
        }
        startPoint -= min;

        // erase sqaureInt
        for (ll j = startPoint; j <= max - min; j += square) {
            squareInt[j] = true;
        }
    }

    int retval = 0;
    for (int i = 0; i <= max - min; ++i) {
        if (squareInt[i] == false) {
            ++retval;
        }
    }
    printf("%d\n", retval);

    return 0;
}

• sqrtMax : $\sqrt{\text{max}}$ 보다 작거나 같은 가장 큰 자연수를 기록