Đếm số 0 đuôi trong giai thừa của một số trong C++

Cho một số nguyên number làm đầu vào. Mục tiêu là tìm số lượng số 0 đuôi trong giai thừa được tính cho số đó. Giai thừa của một số N là tích của tất cả các số trong khoảng [1, N].

Chúng ta biết rằng ta chỉ được số 0 đuôi nếu số đó là bội của 10 hoặc có cặp thừa số (2,5). Trong tất cả các giai thừa của bất kỳ số nào lớn hơn 5, ta có số lượng 2 nhiều hơn 5 trong phân tích thừa số nguyên tố của số đó. Chia số cho các lũy thừa của 5 sẽ cho ta số lượng 5 trong thừa số của nó. Vì vậy, số lượng 5 sẽ cho ta biết số lượng số 0 đuôi.

Ví dụ

Đầu vào

number=6

Đầu ra

Số 0 đuôi trong giai thừa của một số là: 1

Giải thích

Giai thừa là 30. Thừa số nguyên tố của 30: 2 * 3 * 5. Vậy chỉ có một cặp (2,5) tồn tại nên số 0 đuôi là 1.

Đầu vào

number=12

Đầu ra

Số 0 đuôi trong giai thừa của một số là: 2

Giải thích

Giai thừa là 479001600. Thừa số nguyên tố: 2^10 x 3^5 x 5^2 x 7^1 x 11^1. Ta có 2 cặp (2,5) nên số 0 đuôi là 2.

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ chia số cho các lũy thừa của 5. Nếu kết quả lớn hơn 1 thì số 0 đuôi sẽ là số lượng 5. Cộng giá trị này vào biến đếm.

• Nhận số nguyên number làm đầu vào.
• Hàm trailing_zeros(int number) nhận number và trả về số 0 đuôi trong giai thừa của số.
• Khởi tạo biến đếm ban đầu là 0.
• Sử dụng vòng lặp for, chia số cho các lũy thừa của 5.
• Nếu number/i lớn hơn hoặc bằng 1, cộng giá trị này vào biến đếm.
• Trả về biến đếm làm kết quả ở cuối vòng lặp.

Ví dụ mã

#include <iostream> 
using namespace std; 

int trailing_zeros(int number) {
    int count = 0;
    
    for (int i = 5; number / i >= 1; i *= 5) {
        int temp = number / i;
        count = count + temp;
    }
    
    return count;
}

int main() {
    int number = 50;
    cout << "Số 0 đuôi trong giai thừa của một số là: " << trailing_zeros(number);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số 0 đuôi trong giai thừa của một số là: 12