C++程序设计:分解质因数
【问题描述】
题目:将一个正整数分解质因数。例如:输入90,打印出90=233*5。
【输入形式】
输入正整数n
【输出形式】
输出正整数n的因式分解项,如果不能分解,则输出“no answer”
【样例输入】
90
【样例输出】
90=233*5
#include <iostream>
#include <iomanip>
using namespace std;
void answer(int n) {
int j;
bool x=false;
for(j=2; j<n; j++) {
if(n%j==0) {
cout<<"*"<<j;
x=true;
answer(n/j);
break;
}
}
if(x==false)
cout<<"*"<<n;
}
int main() {
int n=1,i;
bool x=false;
cin>>n;
for(i=2; i<n; i++)
if(n%i==0) {
cout<<n<<"="<<i;
x=true;
answer(n/i);
break;
}
if(x==false)
cout<<"no answer";
return 0;
}
这里有一个小技巧:我们在分解的过程中并不需要判断哪些数是质数。直接递归分解就可以,得到的结果中一定都是质数。这是因为如果得到的某个因数不是质数,那么它肯定在这之前就被分解了,不会存在。