[PTA]1059 Prime Factors（分解质因数）

分析：质因数分解，开始写的时候出现的问题，就是判断一个素数出现了几次，我采用了ha[maxn]，但是可能一个大素数有10位，数组存不下。可以采用结构体，存储这个数和这个数出现的次数。
好像数据太弱了，这道题目侥幸过了。。。

#include<bits/stdc++.h>
#define maxn 500010
using namespace std;
typedef long long ll;
ll prime[maxn],n,ha[maxn];
vector<ll> a,b,c;
void db(){
    memset(prime,0,sizeof(prime));for(ll i=2;i<maxn;i++)if(!prime[i])for(ll j=2*i;j<maxn;j+=i)prime[j]=1;
}
int main(){
    std::ios::sync_with_stdio(false);db();cin>>n;if(n==1){
    cout<<"1=1"<<endl;return 0;}cout<<n<<"=";int ans=sqrt(n);for(ll i=2;i<maxn;i++){
    if(n==0) break;if(!prime[i]){
    while(1){
    if(n%i==0&&n!=0){
    if(ha[i]==0){
    a.push_back(i);}ha[i]++;n=n/i;}if(n%i!=0||n==0) break;}}}for(ll i=0;i<a.size()-1;i++){
    ll tt=ha[a[i]];if(tt==1){
    cout<<a[i]<<"*";}else if(tt>1){
    cout<<a[i]<<"^"<<tt<<"*";}}ll lastOne=a[a.size()-1];ll tmp=ha[lastOne];if(tmp==1){
    cout<<lastOne;}else if(tmp>1){
    cout<<lastOne<<"^"<<tmp;}return 0;
}