4395: 【基础】质因子2(2137)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：25
解决：15
题目描述
任意输入一正整数 ，求出它的所有质因子。如：，。
输入
输入只有一行，包括1个整数n (1<n≤109 )。
输出
输出若干行，按从小到大的顺序给出这个数的所有质因子，每行一个。
样例输入 复制
36样例输出 复制
2
2
3
3提示
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
//在2~sqrt(n)的范围内找质因子
for(int i=2;i<=sqrt(n);i++){
//当i是n的因子时，i是质因子，从n中除掉i
while(n%i==0){
cout<<i<<endl;
n=n/i;
}
}
//如果最后x不是1，n也是质因子
if(n!=1) cout<<n;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int Decomposition(int x, int a[]){
//分解 x，数组a升序记录所有质数
//函数值返回分解出来的质数数量
int cnt=0;
//在2~sqrt(x)的范围内找质因子
for(int i=2;i<=sqrt(x);i++){
//当i是x的因子时，i是质因子，从x中除掉i
while(x%i==0){
a[++cnt]=i;
x=x/i;
}
}
if(x!=1) a[++cnt]=x; //如果最后x不是1，x也是质因子
return cnt;
}
int main(){
int n,a[110];
cin>>n;
int s=Decomposition(n,a);
for(int i=1;i<=s;i++)
cout<<a[i]<<endl;
return 0;
}