백준 1016번 제곱 ㄴㄴ 수 c++ 풀이

문제

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

입력

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

출력

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

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

예제 입력 1 복사

1 10

예제 출력 1 복사

7

예제 입력 2 복사

15 15

예제 출력 2 복사

1

예제 입력 3 복사

1 1000

예제 출력 3 복사

608

 

 

에라토스테네스 응용 문제

 

특이한 점 

1. 숫자의 범위가 1조이지만 최솟값과 최댓값의 차이는 1000001 이기 때문에 이 점을 이용해서 배열을 선언할 수 있다.

2. 숫자가 굉장히 크기 때문에 처음부터 제곱 ㄴㄴ 수를 체크하기 시작하면 시간초과가 걸린다. 따라서 시작값인 min에 최대한 근접한 값부터 제곱 ㄴㄴ 수를 체크하기 위해서 N = min / i * i 를 해 주게 된다. 이렇게 되면 i * i에 N을 곱하게 되면 최대한 min에 근접한 값을 얻을 수 있게 된다. 하지만 만약에 N을 i * i 로 나누었을 때 나머지가 0이 아니라면 N을 하나 올려주어야 한다. 왜냐하면 나머지가 생겼다는 뜻은 min보다 작다는 뜻이기 때문이다. 1을 올려주면 min보다 크면서 가장 근접한 제곱 ㄴㄴ 수를 구할 수 있는 N이 구해지게 된다.

3. 이와 에라토스테네스의 응용을 이용하여 N을 하나씩 올려주면서 제곱 ㄴㄴ 수를 0으로 체크해 준다. 그 후 제곱 ㄴㄴ 수가 아닌 수들을 카운트해서 정답을 출력하면 된다.

 

- c++ 풀이

#include <bits/stdc++.h>

using namespace std;

long long num[1000001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long min, max;
    cin >> min >> max;

    for (long long i = 0; i <= max-min; i++) {
        num[i] = i;
    }

    for (long long i = 2; i * i <= max; i++) {
        long long N = min / (i * i);

        if (min % (i * i) != 0)
            N++;

        while (N * i * i <= max) {
            num[N * i * i - min] = 0;
            N++;
        }
    }

    int ans = 0;
    for (long long i = 0; i <= max-min; i++) {
        if (num[i] != 0) {
            ans++;
        }
    }
    cout << ans << "\n";


}