怎樣快速求出前1到n中某一個素因子x出現的次數？

01-05

eg：x=2時
ans2 = 0 + 1//2的指數為1
ans3 = ans2 + 0//2的指數為0

ans4 = ans3 + 2 //2的指數為2
ans5 = ans4 + 0
……
ans(n) = ans(n-1) + [2的指數]

###########
是否有複雜度更加優秀的演算法呢？

謝邀. 原題等價於求素數 $p$ 在 $n!$ 的素因數展開中的冪次，我們將其記為 $alpha_p(n)$

Legendre定理： $alpha_p(n)=sum_{k=1}^{infty}[frac{n}{p^k}]$

證明很簡單，留做習題了……（逃）

（感謝評論提醒，應該是Legendre定理，已改(?&> &

上次牛客網做了一道類似的題目, 其實如果只是求的話, 就是

ans = 0; while(n) { ans += n / x; n /= x; }

(逃)