[백준] 1016번: 제곱 ㄴㄴ 수

1016번: 제곱 ㄴㄴ 수

문제

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

입력

첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다.

출력

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

예제 입력 1 복사

1 10

예제 출력 1 복사

7

 

에라토스테네스의 체 문제가 익숙하다면, 문제를 보고 어 비슷한데, 라는 생각을 했을 것 같습니다. 

제곱ㄴㄴ수의 규칙을 에라토스테네스의 체를 해결하는 방식에 접목시켜서 문제를 풀어나가면 되는데요.

이 문제가 조금 까다로운 것은, min과 max 값의 범위를 처리하는 부분일 것 같기도 합니다.

굉장히 큰 수이기 때문에 min, max의 범위를 0부터 max - min 값으로 대치시켜 생각하여 문제를 해결했습니다. 

 

#include <iostream>
using namespace std;

bool sieve[1000001];

int main() {
    long long m, M;
    cin >> m >> M;

    long long ans = M - m + 1;
    for (long long i = 2; i * i <= M; i++) {
        long long start = m % (i * i) == 0 ? 0 : i * i - (m % (i * i));

        for (long long j = start; j <= M - m; j += i * i) {
            if (!sieve[j]) {
                ans -= 1;
                sieve[j] = true;
            }
        }
    }
    cout << ans << '\n';

    return 0;
}