Prime factorization of a number【1月19日学习笔记】

//Prime factorization of a number
#include<iostream>
#include<cmath>
using namespace std;

void primefactorization(int n) {
	for (int i = 2; i <= sqrt(n); i++) {//质因数（除去本身）只可能在根号n及其左侧
		if (n % i == 0) {//i从2开始，短除法
			int count = 0;
			while (n % i == 0) {//连续除以i至不能整除
				n = n / i;
				count++;//记录指数
			}
			cout << i << "^" << count << " ";
		}
	}
	if (n != 1)  cout << n << "^" << 1;//最终的商，1或质因数（因为上面只循环到了根号n，所以会出现商为1的情况）
	cout << endl;
}//时间复杂度：O(sqrt(n))

int main() {
	int n;
	cin >> n;
	primefactorization(n);
}