分解质因数算法是一种很重要的数论算法。

        代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n / 2; i++) {
        if (n % i == 0) {
            cout << i << " ";
            n /= i--;
        }
    }
    cout << n << endl;
    return 0;
}

        算法通俗易懂。易知第一个可以整除n的i必然是n最小的质因数，这时我们将其输出，并令n除掉i，再令i自减1以在后来的循环中消除n的所有i因子。最后的n将成为一个质数，循环将退出，再将剩下的n输出即可。
        时间与n的大小呈对数关系。