alan23273850 的刷題筆記
a010: 因數分解
Tags: factor
出處：https://zerojudge.tw/ShowProblem?problemid=a010
提交：https://zerojudge.tw/Submissions?problemid=a010&account=allllllan123456
問題：輸出一個大於 1 且不超過 100000000 的正整數的標準分解式。
解法：就從 2 開始除，同時統計次數，等到不整除的時候再輸出前一個階段的 (質數 ^ 次數)。這題實作上有個技巧就是我們可以在 n 除到只剩下 1 的時候順便把最後一個階段的 (質數 ^ 次數) 印出來，所以 while 迴圈不用特別排除掉 n 為 1 的情況。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 bool first = true;
6 int p=2, cnt=0, n; cin >> n;
7 while (true)
8 if (n % p) {
9 if (cnt) {
10 if (!first) cout << " * ";
11 cout << p;
12 if (cnt > 1) cout << '^' << cnt;
13 first = false;
14 }
15 p++; cnt = 0;
16 if (n == 1) break;
17 } else n /= p, cnt++;
18 return 0;
19}