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

Khái niệm

Đối với hai số P và Q đã cho (P và Q có thể lên đến 10 ^ 6) tạo thành một sốN =(P! / Q!). Nhiệm vụ của chúng ta là 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ể. Hãy nhớ rằng, trong mỗi phép toán, người ta có thể thay thế N bằng N / X nếu N chia hết cho X. Hãy xác định số phép toán tối đa có thể thực hiện được.

Đầu vào

A = 7, B = 4

Đầu ra

Giải thích

N là 210 và các ước là 2, 3, 5, 7

Đầu vào

A = 3, B = 1

Đầu ra

Giải thích

N là 6 và số chia là 2,3.

Phương pháp

Người ta đã quan sát thấy rằng sự thừa số hóa của số P! / Q! điều này có giống như thừa số hóa các số (Q + 1) * (Q + 2) *… * (P - 1) * P.

Cũng cần lưu ý rằng, số lượng phép toán sẽ là tối đa nếu chúng ta chỉ chia N với các thừa số nguyên tố của nó. Do đó, nói cách khác, chúng ta cần xác định số lượng các thừa số nguyên tố của N bao gồm cả các số trùng lặp.

Giả sử đếm số thừa số nguyên tố trong phân thừa của mọi số từ 2 đến 1000000.

Đầu tiên, hãy triển khai Sieve of Eratosthenes để xác định một ước số nguyên tố của mỗi số này. Nó được giải thích như sau -

Xây dựng danh sách các số nguyên liên tiếp từ 2 đến N:(2, 3, 4,…, N).
Lúc đầu, giả sử p bằng 2, số nguyên tố đầu tiên.
Bắt đầu từ p ^ 2, đếm theo số gia của p và cho biết mỗi số này lớn hơn hoặc bằng chính p ^ 2 trong danh sách. Vì vậy, những con số này có thể là p (p + 1), p (p + 2), p (p + 3), v.v.
Xác định số đầu tiên lớn hơn p trong danh sách không được chỉ ra. Nếu không có số đó, hãy dừng lại. Nếu không, giả sử p bây giờ bằng số này (cho biết số nguyên tố tiếp theo) và lặp lại từ bước 3.

Sau khi thực hiện phương pháp Sieve of Eratosthenes, chúng ta có thể tính số thừa số nguyên tố trong quá trình phân tích nhân tử của một công thức sau đây -

primefactors [num] =primefactors [num / primedivisor [num]] + 1At hiện tại, người ta có thể triển khai mảng tổng tiền tố cho các thừa số nguyên tố và sau đó trả lời cho khoảng tổng onan [P, Q].

Ví dụ

// CPP program to find maximum
// number moves possible
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
// Used to store number of prime
// factors of each number
int primeFactors1[N];
// Shows Function to find number of prime
// factors of each number
void findPrimeFactors(){
   for (int a = 2; a < N; a++)
   // Now if a is a prime number
   if (primeFactors1[a] == 0)
      for (int b = a; b < N; b += a)
         // Now increase value by one from
         // it's preveious multiple
   primeFactors1[b] = primeFactors1[b / a] + 1;
   // Build prefix sum
   // this will be helpful for
   // multiple test cases
   for (int a = 1; a < N; a++)
      primeFactors1[a] += primeFactors1[a - 1];
}
// Driver Code
int main(){
   // Create primeFactors1 array
   findPrimeFactors();
   int P = 7, Q = 4;
   // required answer
   cout << primeFactors1[P] - primeFactors1[Q];
   return 0;
}