Zerojudge a010. 因數分解

題目連結

題意

給一個整數 n ，將 n 質因數分解並輸出出來

解題方法

因為這題只有問一個數字，數字範圍只到 10^8，我們可以暴力跑過所有可能的因數直接計算每個有幾個

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    int mxn = n;
    bool first = true;
    for(int i = 2;i <= mxn;i++){
	    int cnt = 0;
	    while(n % i == 0){
	        n /= i;
	        cnt ++;
	    }
	    if(cnt >= 1){
	        if(!first) cout << " * ";
	        first = false;
	        if(cnt > 1) cout << i << '^' << cnt;
	        else cout << i;
	    }
    }
}

其實有興趣的讀者會發現，一個範圍裡面可能出現的質數是有限的 (詳細請到這裡看)。

但是，上面的寫法如果遇到數字範圍比較小，詢問比較多的時候這樣的話就會超時。這邊的話就要用另外一種寫法，要先利用質數篩法預處理 (O(n log n) 複雜度所以 n 不能太大)，這樣就可以每個詢問都在 O(log n) 解決，總複雜度就會變成 O(qlogn)。想要知道作法的話在留言告訴我，我會盡快產出 XD

圖片來源：https://www.junyiacademy.org/junyi-math/men/menyb/menzs6a/v/_3R2Tt-WwsU