Tìm các phép toán tối đa để giảm N xuống 1 trong Python

Giả sử chúng ta có hai số P và Q và chúng tạo thành một số N =(P! / Q!). Chúng ta phải giảm N xuống 1 bằng cách thực hiện số lượng phép toán tối đa có thể. Trong mỗi phép toán, người ta có thể thay N bằng N / X khi N chia hết cho X. Chúng ta sẽ trả về số phép toán tối đa có thể.

Vì vậy, nếu đầu vào là A =7, B =4, thì đầu ra sẽ là 4 vì N là 210 và các ước là 2, 3, 5, 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• N:=1000005

• factor:=một mảng có kích thước N và điền bằng 0

• Từ phương thức chính, thực hiện như sau -

• đối với tôi trong phạm vi từ 2 đến N, hãy thực hiện

  • nếu các hệ số [i] giống 0 thì

    • đối với j trong phạm vi i đến N, cập nhật từng bước theo i, thực hiện

      • factor [j]:=factor [j / i] + 1

• đối với tôi trong phạm vi từ 1 đến N, hãy thực hiện

  • yếu tố [i]:=yếu tố [i] + yếu tố [i - 1];

• hệ số trả về [a] - nhân tố [b]

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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])

Đầu vào

7,4

Đầu ra

4