计算阶乘的尾随零

Question

我正在尝试计算阶乘产生的数字的尾随零（这意味着数字变得很大）。以下代码采用一个数字，计算该数字的阶乘，并计算尾随零。但是，当数字大约为25！时，numZeros将不起作用。

public static void main(String[] args) {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    double fact;
    int answer;

    try {
        int number = Integer.parseInt(br.readLine());
        fact = factorial(number);
        answer = numZeros(fact);
    }
    catch (NumberFormatException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    }
}

public static double factorial (int num) {
    double total = 1;
    for (int i = 1; i <= num; i++) {
        total *= i;
    }
    return total;
}

public static int numZeros (double num) {
    int count = 0;
    int last = 0;

    while (last == 0) {
        last = (int) (num % 10);
        num = num / 10;
        count++;
    }

    return count-1;
}

我并不担心这段代码的效率，并且我知道有多种方法可以使这段代码的效率更好。我要弄清楚的是为什么计数大于25的数字结尾的零！不管用。

有任何想法吗？

Answer 1

您的任务不是计算阶乘，而是计算零的数量。一个好的解决方案使用http://en.wikipedia.org/wiki/Trailing_zeros中的公式（您可以尝试证明）

def zeroes(n):
    i = 1
    result = 0
    while n >= i:
        i *= 5
        result += n/i  # (taking floor, just like Python or Java does)
    return result

希望您可以将此翻译为Java。这仅计算[n / 5] + [n / 25] + [n / 125] + [n / 625] +
…，并在除数大于n时停止。

不要使用BigIntegers。这是一个bozosort。这样的解决方案需要大量时间才能实现。