문제

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

입력

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

출력

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

제한

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

접근 과정

소수의 제곱수로 나누어 떨어지지 않는 수라면 다른 어떤 제곱수로 나눠도 나누어 떨어지지 않을 것이기 때문에 소수를 구한뒤 해당 범위 내의 수 중 소수의 제곱수로 나누어 떨어지지 않는 갯수를 구하면 정답을 구할 수 있을 것 같았다.
속도 같은건 생각하지 않고 가능한 간단하게 소수(정확히는 소수의 제곱)을 벡터에 저장하여 1의 아이디어와 같이 구현해보았다. 출력 결과는 잘 나왔으나 범위를 최대로 잡았을 때 속도가 너무 느렸다. 계산량이 늘어나니 큰 정수의 나눗셈 연산이 부하가 컷던 모양.
에라토스테네스의 체를 통해 소수를 구하듯 에라토스테네스의 체와 같은 방식으로 범위내의 숫자에 대해 소수의 제곱수로 나누어 떨어지는지 확인한다. 이렇게 구현하면 부하가 큰 나눗셈 연산이 소수의 갯수만큼만 수행되므로 속도를 획기적으로 높일 수 있다.

다루는 수의 크기에 따라 자료형을 잘 신경써야겠다. 습관적으로 반복문을 쓸 때 unsigned int 를 사용했다가 이유도 모르고 여러번 틀리고 말았다 -_-;;

소스 코드

#include <iostream>
using namespace std;

int primeNumbers[1001000];
int powerNoNoNumbers[1001000];

int solution(unsigned long sqrtMax, unsigned long base, unsigned long offsetMax) {
    int ret = offsetMax + 1;

    for (unsigned long num = 2; num <= sqrtMax; ++num) {
        if (primeNumbers[num] == 0) {
            // 에라토스테네스의 체를 통한 소수 구하기
            for (unsigned long i = num + num; i <= sqrtMax; i += num) {
                primeNumbers[i] = 1;
            }

            // 소수의 제곱수를 구하고 범위 내에서 제곱수로 나누어 떨어지는 수의 위치를 구함
            unsigned long powerNum = (unsigned long) num * num;
            unsigned long offset = powerNum - (base % powerNum);
            if (offset == powerNum) { offset = 0; }

            // 해당 위치부터 제곱수 단위로 제거
            while (offset <= offsetMax) {
                if (powerNoNoNumbers[offset] == 0) {
                    powerNoNoNumbers[offset] = 1;
                    --ret;
                }
                offset += powerNum;
            }
        }
    }
    return ret;
}

int main() {
    unsigned long min, max;
    unsigned long sqrtMax = 1;
    cin >> min >> max;
    
    while (sqrtMax * sqrtMax < max) { ++sqrtMax; }

    cout << solution(sqrtMax, min, max - min);
    return 0;
}