Đếm số phép toán giảm N về 0 bằng cách trừ ước nguyên tố nhỏ nhất trong C++

Cho số nguyên dương N. Tìm số phép toán để giảm N về 0. Phép toán: N = N - P với P là ước nguyên tố nhỏ nhất của N hiện tại.

Ví dụ

Đầu vào − N = 17

Đầu ra − 1

Giải thích − 17 là số nguyên tố, ước nhỏ nhất là 17. 17-17=0, 1 phép.

Đầu vào − N = 20

Đầu ra − 10

Giải thích − Ước nhỏ nhất của 20 là 2. Trừ 2 liên tục: 20→18→16→...→2→0, 10 phép.

Phương pháp giải

Số chẵn luôn có ước nguyên tố nhỏ nhất là 2. Số lẻ có ước lẻ, sau khi trừ thành số chẵn thì ước là 2. Tìm ước nhỏ nhất i từ 2 sao cho i*i < N và N%i==0. Nếu không tìm thấy → i = N. Số phép = 1 + (N-i)/2.

• Hàm N_to_Zero(int N).
• i = 2, while i*i < N && N%i != 0: i++.
• Nếu i*i > N → i = N.
• count = 1 + (N-i)/2.
• Trả về count.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

int N_to_Zero(int N) {
    int count = 0;
    int i = 2;
    while ((i * i) < N && (N % i)) i++;
    if ((i * i) > N) i = N;
    count = 1 + (N - i) / 2;
    return count;
}

int main() {
    int N = 10;
    cout << "Count of operations of the given type required to reduce N to 0 are: " << N_to_Zero(N);
    return 0;
}

Đầu ra

Count of operations of the given type required to reduce N to 0 are: 5