【範例】最大質因數建表
【題目敘述】 https://open.kattis.com/problems/nonprimefactors
- 先建表：找出所有數的最大質因數。
- 對輸入的數進行質因數分解，從其最大質因數開始。
- 【例】
- 100 = 5^2 * 2^2 （100 有兩個質因數：5 和 2。）
- 可知 100 有 (2+1)*(2+1) = 9 個因數：1, 2, 4, 5, 10, 20, 25, 50, 和 100。
- 其中，2 和 5 是質數。因此，100 有 9 – 2 = 7 個非質數的因數。
#include <iostream>
using namespace std;
const int maxn = 2000005;
int mx_prime[maxn];
void tbl_mx_prime(){
// 建表:找出所有數的最大質因數
mx_prime[0] = 0;
mx_prime[1] = 1;
for (int i=2; i<maxn; i++){
if (mx_prime[i] > 0) continue;
for (int j=i; j<maxn; j+=i){
mx_prime[j] = i;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int Q, N;
tbl_mx_prime();
cin >> Q;
while (Q--){
cin >> N;
int last_pf = 0; //前一個質因數
int n_pf = 0; //可分解成幾種質因數的連乘積
int cnt = 0; //連續質因數的個數
int ans = 1;
// 質因數分解，e.g. 100 = 2^2 * 5^2
// 共有(2+1)*(2+1)個因數，其中有兩個是質因數
while (N > 1){
if (mx_prime[N] == last_pf) cnt++;
else {
ans *= (cnt + 1);
last_pf = mx_prime[N];
n_pf++;
cnt = 1;
}
N /= mx_prime[N];
}
ans *= (cnt + 1);
cout << ans - n_pf << '\n';
}
return 0;
}