Python에서 N을 1로 줄이는 최대 연산 찾기

두 개의 숫자 P와 Q가 있고 숫자 N =(P!/Q!)를 형성한다고 가정합니다. 가능한 최대 연산을 수행하여 N을 1로 줄여야 합니다. 각 연산에서 N을 X로 나눌 때 N을 N/X로 바꿀 수 있습니다. 가능한 최대 연산 수를 반환합니다.

따라서 입력이 A =7, B =4와 같으면 N이 210이고 제수가 2, 3, 5, 7이므로 출력은 4가 됩니다.

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

N :=1000005
factor :=크기가 N이고 0으로 채워지는 배열
기본 방법에서 다음을 수행하십시오 -
범위 2에서 N까지의 i에 대해 수행
- factor[i]가 0과 같으면
  - 범위 i에서 N까지의 j에 대해 i만큼 각 단계에서 업데이트합니다.
    - factor[j] :=factor[j / i] + 1
범위 1에서 N까지의 i에 대해 수행
- factor[i] :=factor[i] + factor[i - 1];
반환 요소[a] - 요소[b]

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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