4396: 【入门】质因子3(2140)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：12
解决：6
题目描述
给定一个整数 ，找出它的所有质因子，并按如下格式输出：
。
注意: 如果 则输出 。
在程序的实际输出时，写作：。
其中 是质因子，应按照递增顺序排列， 是 的指数，如果 为 ，则不必输出。
比如：如果 ，那么输出：。
再比如：如果 ，那么输出：。
输入
一个整数 。（）
输出
按题意输出分解结果。
样例输入 复制
100样例输出 复制
100=2^2*5^2提示
#include<bits/stdc++.h>
using namespace std;
/*
求质因数及质因数出现的次数
1.采用map<int,int>存储质因数及出现的次数
2.按题意输出规定的格式
*/
int n,ma; //ma存储最大的质因子
map<int,int> m;
map<int,int>::iterator it;
int main(){
cin>>n;
if(n==1) {
cout<<"1==1";
return 0;
}
cout<<n<<"=";
/*
分解质因数
i*i<=n，因为如果i很大,i*i会溢出int
*/
for(int i=2;i<=sqrt(n);i++){
while(n%i==0){
m[i]++;
n=n/i;
ma=i;
}
}
if(n>1) {
m[n]++;
ma=max(ma,n);
}
for(it=m.begin();it!=m.end();it++){
cout<<it->first;
if(it->second>1) cout<<"^"<<it->second;
//如果不是最后一组输出（不是最大的质因子）
if(it->first!=ma) cout<<"*";
}
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是n的因子时，i是质因子，从n中除掉i
while(x%i==0){
a[++cnt]=i;
x=x/i;
}
}
//如果最后n不是1，x也是质因子
if(x!=1) a[++cnt]=x;
return cnt;
}
int main(){
int n,a[110];
cin>>n;
if (n==1) {
cout<<"1=1";
return 0;
}
a[0]=1;
int s=Decomposition(n,a);
int p=0,first=1;
cout<<n<<"=";
for(int i=1;i<=s;i++) {
if (a[i]!=a[i-1]) {
if(p>1) {
cout<<"^"<<p;
}
if (!first) {
cout<<"*";
}
cout<<a[i];
if (first) first=0;
p=1;
}else {
p++;
}
if (i==s && p>1) cout<<"^"<<p;
}
return 0;
}