G07 分解质因数 唯一分解定理 试除法

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
struct node{int x,k;}a[100];int alen;
int p[N],pr;bool v[N+10];
void init()
{
	pr=0;memset(v,0,sizeof(v));
	for(int i=2;i<=N;i++)
	{
		if(v[i]==0)p[++pr]=i;
		for(int j=1;j<=pr&&i*p[j]<=N;j++)
		{
			v[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}
int main()
{
    init();
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(v[n]==0){printf("YES\n");continue;}
        printf("%d=",n);
        alen=0;
        for(int i=1;i<=pr;i++)
        {
        	if(n%p[i]==0)
        	{
        		a[++alen]=node{p[i],0};
        		while(n%p[i]==0)
        		{
        			a[alen].k++;
        			n/=p[i];
        		}
        	} 
        }
        
	    for(int i=1;i<alen;i++)
	    {
	        if(a[i].k==1)printf("%d*",a[i].x);
	        else printf("%d^%d*",a[i].x,a[i].k);
	    }
	    if(a[alen].k==1)printf("%d\n",a[alen].x);
	    else printf("%d^%d\n",a[alen].x,a[alen].k); 
    }
    return 0;
}