alan23273850 的刷題筆記
d131: 00160 - Factors and Factorials
Tags: factor
出處：https://zerojudge.tw/ShowProblem?problemid=d131
提交：https://zerojudge.tw/Submissions?problemid=d131&account=allllllan123456
問題：這題要請你求出多個介於 2 到 100 的整數 $N$ 之階乘 $N!$ 的標準分解式。
解法：要求出每個質數 $p$ 出現的次數，只要加總 $\lfloor N/p\rfloor$ + $\lfloor N/p^2\rfloor$ + $\lfloor N/p^3\rfloor$ + … 即可。
1#include <bits/stdc++.h>
2using namespace std;
3
4const int p[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
5
6int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
7 int n;
8 while (cin >> n && n) {
9 cout << setw(3) << n << "! =";
10 for (int i=0; i<25; i++) {
11 int p2 = p[i], t = 0;
12 while (p2 <= n)
13 t += n / p2,
14 p2 *= p[i];
15 if (!t) break;
16 if (i == 15) cout << "\n ";
17 cout << setw(3) << t;
18 }
19 cout << '\n';
20 }
21 return 0;
22}