Python으로 N을 1로 줄이는 최대 연산 횟수 구하기

문제 설명

두 수 P와 Q가 있으며, 이 두 수로 N = (P!/Q!)라는 수를 만든다고 가정해 보겠습니다. 목표는 가능한 한 많은 연산을 수행하여 N을 1로 줄이는 것입니다. 각 연산에서는 N이 X로 나누어떨어지는 경우 N을 N/X로 대체할 수 있으며, 가능한 최대 연산 횟수를 반환해야 합니다.

예를 들어 입력이 A = 7, B = 4라면 출력은 4가 됩니다. 이 경우 N은 210이며, 소인수가 2, 3, 5, 7로 총 4개이기 때문입니다.

접근 방법

이 문제를 해결하기 위해 다음 단계를 따릅니다.

N := 1000005로 설정합니다.
factors := 크기가 N인 배열을 선언하고 모든 값을 0으로 초기화합니다.
메인 메서드에서 다음 작업을 수행합니다.
i를 2부터 N까지 반복합니다.
- factors[i]가 0이라면(i가 소수라면):
  - j를 i부터 N까지 i씩 증가시키며 반복합니다.
    - factors[j] := factors[j / i] + 1로 갱신합니다.
i를 1부터 N까지 반복합니다.
- factors[i] := factors[i] + factors[i - 1]로 누적합을 계산합니다.
factors[a] - factors[b]를 반환합니다.

동작 원리

핵심 아이디어는 N = P!/Q! = (Q+1) × (Q+2) × ... × P이므로, N의 소인수 총개수는 Q+1부터 P까지 각 수가 가진 소인수 개수의 합과 같다는 점입니다. 또한 매 연산에서 N을 소수로 나눌 때마다 소인수가 하나씩 사라지므로, 최대 연산 횟수는 곧 N의 전체 소인수 개수(중복 포함)가 됩니다.

에라토스테네스의 체와 유사한 방식으로 각 수의 소인수 개수를 미리 구해 두고, 여기에 누적합(prefix sum)을 적용하면 factors[a] - factors[b]를 통해 구간 [b+1, a]에 속한 수들의 소인수 개수 합을 O(1) 시간에 얻을 수 있습니다.

예제 코드

더 잘 이해하기 위해 다음 구현을 살펴보겠습니다.

N = 1000005
factors = [0] * N;

def get_prime_facts() :
    for i in range(2, N) :
        if (factors[i] == 0) :
            for j in range(i, N, i) :
                factors[j] = factors[j // i] + 1
    for i in range(1, N) :
        factors[i] += factors[i - 1];

get_prime_facts();
a = 7; b = 4;
print(factors[a] - factors[b])

입력

7, 4