alan23273850 的刷題筆記
d121: 00583 - Prime Factors
Tags: factor
出處：https://zerojudge.tw/ShowProblem?problemid=d121
提交：https://zerojudge.tw/Submissions?problemid=d121&account=allllllan123456
問題：輸出一個不為 0 之 int 整數的質因數分解式。
解法：這題和 a010 一樣都是要求一個數字的質因數分解，只是這題包含負整數而且範圍更涵蓋到整個 int。事實上只要比 a010 再多兩個步驟就能 AC 而且效率不會到太差，第一動是如果遇到負數的話就先把它除掉，第二動是程式碼 17-18 行的地方，只要發現欲除以的質數 p 已經大於剩餘因數 n 的平方根 $\sqrt n$，那麼 n 必為質數，我們便可以從迴圈中跳停，這一動非常重要，它是從 3s 的 TLE 壓到 33ms AC 的關鍵！而且不用建質數表。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 int n;
6 while (cin >> n && n) {
7 int p=2; bool first = true;
8 cout << n << " = ";
9 if (n < 0) {
10 cout << "-1";
11 n = -n;
12 first = false;
13 }
14 while (n > 1)
15 if (n % p) {
16 p++;
17 if (p > sqrt(n))
18 p = n; // this acceleration is very important!!!
19 } else {
20 if (!first) cout << " x ";
21 cout << p;
22 n /= p;
23 first = false;
24 }
25 cout << '\n';
26 }
27 return 0;
28}