นับศูนย์นำหน้าในแฟกทอเรียลของตัวเลขด้วย C++

ได้รับจำนวนเต็มเป็นอินพุต เป้าหมายคือหาจำนวนศูนย์นำหน้า (trailing zeros) ในแฟกทอเรียลของตัวเลขนั้น แฟกทอเรียลของ N คือผลคูณของทุกตัวเลขในช่วง [1, N]

เรารู้ว่าจะได้ศูนย์นำหน้าเมื่อตัวเลขเป็นจำนวนเท่าของ 10 หรือมีคู่ตัวประกอบ (2,5) ในแฟกทอเรียลของตัวเลขที่มากกว่า 5 จำนวน 2 ในการแยกตัวประกอบเฉพาะจะมากกว่า 5 เสมอ การหารตัวเลขด้วยกำลังของ 5 จะให้จำนวน 5 ในตัวประกอบ ดังนั้นจำนวน 5 จะบอกจำนวนศูนย์นำหน้า

ตัวอย่าง

Input

number=6

Output

Count of trailing zeros in factorial of a number are: 1

Explanation

The factorial is 30. Prime factors of 30: 2 * 3 * 5 So only one pair of (2,5) exists so trailing zeros is 1.

Input

number=12

Output

Count of trailing zeros in factorial of a number are: 2

Explanation

The factorial is 479001600. Prime factors of 479001600: 2^10 x 3^5 x 5^2 x 7^1 x 11^1 So we can get 2 pairs of (2,5) so trailing zeros are 2

วิธีการที่ใช้ในโปรแกรม

วิธีนี้หารตัวเลขด้วยกำลังของ 5 ถ้าผลลัพธ์มากกว่าหรือเท่ากับ 1 จำนวนศูนย์นำหน้าจะเท่ากับจำนวน 5 บวกค่านี้เข้า count

• รับจำนวนเต็ม number เป็นอินพุต
• ฟังก์ชัน trailing_zeros(int number) คืนค่าจำนวนศูนย์นำหน้าในแฟกทอเรียล
• กำหนดจำนวนนับเริ่มต้นเป็น 0
• ใช้ลูป for หารตัวเลขด้วยกำลังของ 5
• ถ้า number/i >= 1 บวกค่านี้เข้า count
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#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 << "Count of trailing zeros in factorial of a number are: " << trailing_zeros(number);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of trailing zeros in factorial of a number are: 12