백준 1456 - 거의 소수

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

1456번: 거의 소수

에라토스테네스의 체를 응용한다. 소수를 이용하는 문제라면 꼭 이 아저씨가 나오는 거 같다.

수의 범위가 상당히 크다. 게다가 min과 max의 차이도 얼마든지 커질 수 있다. 이번엔 어떻게 체를 개조해야 할까?

 

하고싶은 말을 위한 빌드업

질문을 하나 던져보자. 에라토스테네스의 체를 구현할 때, 코드를 이렇게 수정하면 판정 배열의 크기를 (sqrt(N) + 1)로 줄일 수 있지 않을까?

 

//코드는 대충 읽어주세요

int rt = sqrt(N);
vector<bool> checked(rt + 1);

int i, j, cnt = N;
for (i = 2; i <= rt; i++) {
    if (!checked[i]) {
        for (j = i * i; j <= max; j += i)
            if(j <= rt)
            	checked[j] = 1;
            cnt--;
        }
    }
}

 

사실 코드가 좀 이상하긴 한데, 소수의 개수를 N으로 설정하고 매번 합성수(소수 ㄴㄴ 수)가 발견될 때마다 1씩 감소시키면 sqrt(N)까지의 소수만으로도 소수의 개수를 구할 수 있지 않냐는 뜻이다.

 

답은 X이다. 하나의 합성수가 여러 조합으로 생성될 수 있으니까. 예를 들어 합성수 60은 2 * 30에서도 발견되고 3 * 20에서도 발견되며 5*12에서도 발견되므로 cnt가 3번이나 감소된다.

 

그럼 합성수가 여러 조합이 아닌 하나의 조합으로만 생성된다면 위 코드를 사용할 수 있을까?

cnt가 중복으로 감소될 일이 없으므로, sqrt(N) + 1 크기의 판정 배열만 가지고도 프로그램을 실행할 수 있을 것이다.

 

소수의 거듭제곱수는 해당 소수에서만 구할 수 있다. 49를 7이 아닌 다른 수들의 곱으로 나타낼 수는 없다. 따라서 위 코드의 아이디어를 적용할 수 있다.

결론적으로, '거의 소수'는 소수를 거듭제곱하는 경우 중복으로 등장하는 경우가 없다. 따라서 cnt를 이용해 개수를 셀 수 있으며, 판정 배열의 크기는 N이 아니라 sqrt(N)으로도 충분하다.

 

에라토스테네스의 체를 개조해, 2부터 sqrt(N)까지의 소수만 구하면서, 매 소수마다 max까지 거듭제곱을 구하며 입력받은 범위에 포함될 경우 cnt를 중가시킨다.

for (j = i * i; j <= max; j *= i) {
    //소수의 제곱은 겹치지 않는다.
    if (j >= min)
        cnt++;

 

다만 j의 자료형을 long long으로 설정해도 오버플로우가 발생할 수 있어 이를 처리해주어야 한다.

max가 10^14이고 i가 10^7보다 조금 작은 소수라고 하자. j = i*i는 10^14 = max보다 작으므로 반복문이 계속 진행된다. i를 한번 더 곱하면 j는 10^21에 근사한 값을 갖는데, long long 자료형의 표현 가능 범위는 최대 9,223,372,036,854,775,807 로 10^21보다 작으므로 오버플로우가 발생할 것이다.

 

표현 가능 범위를 외우기보다는, 2^10 ≒ 10^3 임을 응용하면 쉽다. long long은 유부호 자료형이므로 8바이트, 64비트 중 63비트만 값 표현에 사용한다. 63비트로 표현할 수 있는 최대값은 2^63 = (2^10)^6 * 2^3 ≒ 10^18 * 8 정도라고 생각할 수 있다. 저 근처에 해당된다 싶으면 안전하게 오버플로우를 처리하자.