題目簡述 #
給定一個數字，比如 200 要將 200 的質因數分解輸出：
200 = 2 x 2 x 2 x 5 x 5
除了正整數，還需要處理負數，處理方法是在最前面加上「-1 x」，比如-192：
-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3
質數篩 #
先做一個質數篩的函數出來，我用的是線性篩，關於質數篩我有寫一篇介紹文章，這裡不過多贅述
const int MAX = 1e7+5;
bitset<MAX>isp;
vector<int>primes;
void sieve(int n){
isp.set();
isp[0]=isp[1]=0;
for(int i=2;i<=n;i++){
if(isp[i]){
primes.push_back(i);
}
for(int p : primes){
if(i*p > n)break;
isp[i*p]=0;
if(i%p==0)break;
}
}
}
黑心老闆演算法 #
接下來展示的是用來質因數分解的模板，我把它稱為「黑心老闆演算法」，其程式片段如下：
cin>>n;
int x = abs(n);
vector<int>ciallo;
for(int p : primes){
if(p*p > x) break;
while(x%p==0){
ciallo.push_back(p);
x/=p;
}
}
if(x > 1) ciallo.push_back(x);
把要分解的數 x 想成一間公司，每個質數 p 代表一個派系。老闆（我們）從最小的派系開始清算：
-
只要
x還能被p整除，就代表公司裡還有p派的員工。 -
把這位員工的名字記進名單
ciallo（push_back(p)），然後開除他（x /= p）。 -
同一派系可能有很多人，所以用
while一直開除，直到x再也不能被p整除，才算把這個派系「斬草除根」。 -
換下一個更大的質數，重複以上步驟。
每開除一人，公司（x）就變小一些。最後名單 ciallo 裡的所有數字相乘，就會等於原本的 x。
為什麼 p*p > x 可以停止
先說迴圈的不變式：輪到質數 p 時，x 已經把所有比 p 小的質因數除乾淨了。
此時若 \(p^2 > x\)（\(p > \sqrt(x)\)）：
-
假設 \(x\) 是合數，它必有：質因數 \(\le \sqrt{x} < p\)。
-
但所有小於 \(p\) 的質因數都已經被除掉了，矛盾。
-
所以 \(x\) 只能是 \(1\) 或質數。
因此可以直接停止迴圈。若剩下的 x > 1，它就是最後一個質因數（公司裡剩下的最後一位大佬，自己一派），直接放進名單即可：
if(x > 1) ciallo.push_back(x);
注意這裡的 x 是當前剩下的值，會隨著除法變小。
輸出格式小技巧 #
題目要求質因數之間用 x 隔開，最後一個後面不能多出 x。做法是用 i > 0 判斷：只有從第二個數開始，才在前面補上 x。
cout<<n<<" = ";
if(n < 0) cout<<"-1 x ";
for(int i=0; i<ciallo.size(); ++i){
if(i > 0) cout<<" x ";
cout<<ciallo[i];
}
cout<<'\n';
負數則是在印質因數之前，先額外輸出 -1 x ，這樣後面的迴圈完全不用特別處理負號。
程式 #
#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<cmath>
using namespace std;
const int MAX = 1e7+5; //其實不用開到 1e7+5 這麼大
bitset<MAX>isp;
vector<int>primes;
void sieve(int n){
isp.set();
isp[0]=isp[1]=0;
for(int i=2;i<=n;i++){
if(isp[i]){
primes.push_back(i);
}
for(int p : primes){
if(i*p > n)break;
isp[i*p]=0;
if(i%p==0)break;
}
}
}
int main(){
sieve(90000);
int n;
while(cin>>n&&n){
vector<int>ciallo;
int x = abs(n);
for(int p :primes){
if(p*p > x){
break;
}
if(x%p==0){ //註記：if(x%p==0) 其實是多餘的，只是另一題類似的 UVA-10699 需要這個 if
while(x%p==0){
ciallo.push_back(p);
x/=p;
}
}
}
if(x > 1)ciallo.push_back(x);
cout<<n<<" = ";
if( n <0)cout<<"-1 x ";
for(int i=0;i<ciallo.size();++i){
if(i > 0)cout<<" x ";
cout<<ciallo[i];
}
cout<<'\n';
}
}
