java - A 除以 N 阶乘的最高幂是多少？

Question

我试图在 codefights.com 上解决这个问题，方法是找出最大的质因数并将该数字除以质因数的幂。

int highestPower(int N, int A) {
int B =A, j=0,c=0, p=0,x;

for(int i = 2; i<=A; i++) {
    if( A%i == 0) {
        p = i>p ? i:p;
        A/=i;
        --i;
    }
    if(i*i > A && B==A) {
        p = B;
        break;
    }
}

for(;(x = N/((int)Math.pow(p,++j))) > 0; )
    c+=x;
return c;

}

Input:

0<N<10^9
1<A<10^9

但是这种方法对于某些测试用例来说会失败。一个这样的测试用例是:

N:100
A:1024
Output:97
Expected Output:9

关于如何解决这个问题有什么建议吗？

Answer 1

最后一个 for 循环计算 p 除以 N 的幂，但如果 A 因式分解时 p 的幂大于 1，则与所需的答案不同。在给定的示例中，您计算​​出 2^97 除以 100!，但这与您被问到的问题无关。至少你应该在 A 的因式分解中除以 p 的幂(在本例中为 10)，但我不知道在一般情况下这是否足够。