因子分解 C++ 递归、线性筛

解题思路: 用线性筛选出100以内所有素数， 递归分解质因数直至n 等于1

注意事项:注意输出格式控制

参考代码:

#include<iostream>
#include<string>
using namespace std;
const int N = 1e2 + 10;
int prime[N],k;
bool nprime[N]; 
void prime_filter(int n){
	for(int i= 2; i <= n ; i ++ ){
		if(!nprime[i])
			prime[k ++] = i;
		for(int j = 0; j < k && i * prime[j] <= n; j ++){
			nprime[i * prime[j]] = true;
			if(i % prime[j] == 0) break;
		}
	}
}
string s;
void dfs(int n,int k){
	if(n == 1) return;
	int m = 0;
	while(n % prime[k] == 0){
		m ++;
		n /= prime[k];
	}
	if(m > 0) {
		s += to_string(prime[k]);
		if (m > 1) {
			s += "^";
			s += to_string(m);
		}
		if(n > 1) s += "*";
	}	
	dfs(n,k + 1);
}
int main()
{
	prime_filter(100);
	int n; 
	cin >> n;
	dfs(n,0);
	cout << s;
	return 0;
}