欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA:7-110 素因子分解 (20分)

程序员文章站 2022-03-04 22:37:52
...

7-110 素因子分解 (20分)

PTA:7-110 素因子分解 (20分)
输入样例:

1323

输出样例:

1323=3^3*7^2

具体解析见AC代码:
(注意n为1的情况,输出为“1=1”)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll Isprime(ll x){
	ll j=0;
	for(j=2; j<=sqrt(x); j++){
		if(x%j==0) break;
	}	
	if(j>sqrt(x)) return 1;
	return 0;
}

int main(){
	ll n;
	ll cnt=0;
	cin>>n; 
	int m=n;
	cout<<n<<"=";
	for(ll i=2;;i++){
		if(n==1) break;
		if(Isprime(i)){
			cnt=0;
			while(n%i==0){
				cnt++;
				n/=i;						
			}
			if(cnt>0){
				cout<<i;
				if(cnt>1) cout<<"^"<<cnt;		
				if(n>1) cout<<"*";
			} 
		}
	}
	if(m==1) cout<<1;
	return 0;
} 

PTA:7-110 素因子分解 (20分)
欢迎大家批评改正!!!