c++质因数分解

质因数分解，最先想到了遍历1-n，找出既是质数也是因数的数。

需要用到判断质数函数、while循环，复杂度三次方以上了。

#include<iostream>
using namespace std;
bool zs(int n) {
	for (int i = 2; i <= n / 2; i++) {
		if (n % i == 0) {
			return 1;
		}
	}
	return 0;
}
int main() {
	long long n, cnt = 0;
	cin >> n;
	cout << n << "=";
	while (n != 1) {
		for (int i = 2; i <= n; i++) {
			if (!zs(i)) {
				while (n % i == 0) {
					n = n / i;
					if (cnt == 0) {
						cout << i;
						cnt++;
					} else {
						cout << "*" << i;
						cnt++;
					}
				}
			} else {
				continue;
			}
		}
	}
	return 0;
}

第一步优化：实际上，不用判断质数，因为该除的前面也除掉了，所以可以把质数判断删掉。

#include<iostream>
using namespace std;
int main() {
	long long n, cnt = 0;
	cin >> n;
	cout << n << "=";
	while (n != 1) {
		for (int i = 2; i <= n; i++) {
			while (n % i == 0) {
				n = n / i;
				if (cnt == 0) {
					cout << i;
					cnt++;
				} else {
					cout << "*" << i;
					cnt++;
				}
			}
		}
	}
	return 0;
}

第二步优化：前面的代码写i<=n是因为怕这个数是质数，但我们只需写i*i<=n就行，结尾加n大于1的判断，就能进一步优化。

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	cout << n << "=";
	if (n == 1) {
		cout << 1;
		return 0;
	}
	int flag = 0;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			int cnt = 0;
			while (n % i == 0) {
				n = n / i;
				cnt++;
			}
			if (flag == 1) {
				cout << "*";
			}
			if (cnt == 1) {
				printf("%d", i);
			} else {
				printf("%d^%d", i, cnt);
			}
			flag = 1;
		}
	}
	if (n > 1) {
		if (flag == 1) {
			cout << "*";
		}
		printf("%d", n);
	}
	return 0;
}