描述：
给定某个正整数 N，求其素因子分解结果，即给出其因式分解表达式
N = p1k1 * p2k2… pmkm
输入：
输入long int范围内的正整数N。
输出：
pi由小到大输出，当ki==1时可以直接输出pi。
思路：
一个典型的递归求解问题，注意特判输入的数为‘1’即可；
#include<bits/stdc++.h> using namespace std; typedef unsigned long long ull; typedef long long ll; const ll maxx = 1e18; const int N = 1e6+100; const int p = 1e4; const double eps = 1e-8; ll k; ll judge(ll n) { if(n<2) return 0; for(ll i=2;i<=n/i;i++) if(n%i==0) return 0; return 1; }//判断素数 void Prime(ll n) { if(n==1) return ;//递归函数跳出条件，分解到 1 就结束 int cnt=0; for(int i=2;;i++) { if(n%i==0&&judge(i)==1)//是素因数 { cout<<i;//输出这个数 while(n%i==0) { cnt++; n/=i; }//找相同的数的个数 //相同的数个数直接用一个while循环来找，没必要再调用递归 if(cnt==1) { if(n!=1) cout<<"*"; }//没有相同的输出乘号，注意判断这个数不是最后一个数 else { if(n==1) cout<<"^"<<cnt; else cout<<"^"<<cnt<<"*"; }//有相同的输出幂次和乘号，注意判断是不是最后一个 break; } } Prime(n);//再次调用 } int main() { cin>>k; cout<<k<<"="; if(k==1)//特判 1 { cout<<k; return 0; } else Prime(k);//调用函数 return 0; }
反思：
相同的数个数直接用一个while循环来找，没必要再调用递归，节省时间
