题意

给出一个正整数 $n$ ,求它的因数分解式。

思路

$O(n)$ 做法：

枚举从2到$n$，如果是质因子就不断除$n$,直到不能除为止。

$O(\sqrt{n})$ 做法:

枚举时到 $\sqrt{n}$ 即可。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3fffffff;
int main(){
	long long n;
	cin >> n;
	long long nn = n;
	for(long long i = 2;i <= sqrt(n);i++){
		if(n % i == 0){
			int cnt = 0;
			while(n % i == 0){
				n/=i;
				cnt++;
			}
			if(cnt == 1){
				cout << i << " * ";
			}else{
				cout << i << "^" << cnt << " * ";
			}
		}
	}
	if(nn == n){
		cout << n << endl;
	}else {
		if(n != 1) cout << n << endl;
	}
	return 0;
}