AcWing 1545. 质因子——分解质因数
原题链接
简单
作者:
迎风飘扬
,
2022-07-08 14:59:32
,
所有人可见
,
阅读 404
#include<bits/stdc++.h>
using namespace std;
bool ad(long long n){
if(n<2)return false;
for(long long i=2;i*i<=n;i++)if(n%i==0)return false;
return true;
}
int main(){
long long n;
cin>>n;
int k=0;
cout<<n<<"=";
int s=2;
if(n==1){
cout<<1;
return 0;
}
while(n>1){
if(ad(n)){
cout<<n;
break;
}
for(long long i=2;i<=n;i++){
if(ad(i)){
k=i;
if(n%i==0)
break;
}
}
int u =0;
while(n%k==0){
u++;
n/=k;
}
if(u>1){
cout<<k<<"^"<<u;
}
else cout<<k;
if(n!=1)cout<<"*";
}
}