Chúng ta được cho một số nguyên dương N.
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - N =17
Đầu ra - Số lượng các phép toán thuộc loại đã cho được yêu cầu để giảm N xuống 0 là - 1
Giải thích - Ước số nguyên tố nhỏ nhất của 17 là chính nó. Vì vậy, hoạt động chỉ được áp dụng một lần 17-17 =0.
Đầu vào - N =20
Đầu ra - Số lượng phép toán thuộc loại đã cho được yêu cầu để giảm N xuống 0 là - 10
Giải thích - Ước số nguyên tố nhỏ nhất của 20 là 2. Trừ đi 2 lần nữa và tìm ước số nguyên tố tiếp theo:
20%2==0, 20-2=18 18%2==0, 18-2=16 …………………..14, 12, 10, 8, 6, 4, 2, 0 Total 10 times the operation is applied.
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Đối với tất cả N chẵn, ước số nguyên tố nhỏ nhất sẽ luôn là 2 và trừ đi 2 từ N chẵn sẽ lại tạo ra một số chẵn. Đối với tất cả các số lẻ, ước số nguyên tố nhỏ nhất sẽ là số lẻ, sau khi trừ đi số lẻ và số sẽ trở thành số chẵn nên 2 sẽ trở thành ước số nguyên tố nhỏ nhất. Để tìm ước số nguyên tố nhỏ nhất bắt đầu từ i =2 đến i sao cho i * i
Lấy một số nguyên N làm đầu vào.
Hàm N_to_Zero (int N) nhận N và trả về số hoạt động cần thiết để giảm N xuống 0.
Lấy giá trị ban đầu của số đếm là 0.
Bắt đầu từ i =2. Bắt đầu đi ngang khi (i * i)
Nếu (i * i) vượt quá N, hãy đặt i =N.
Số lượng hoạt động sẽ là 1+ (N-i) / 2.
Đặt số lượng là 1+ (N-i) / 2.
Kết quả là số lượt trả lại.
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Ví dụ
#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