质因子分解C++

1、题目

2、AC代码

#include<iostream>
#include<cmath>
using namespace std;

const int maxn=100010;// 10的5次方即可
bool isPrime(int n)
{
    if(n<=1)return false;
    if(n==2 || n==3)return true;// 特判
    if(n%6!=1 && n%6!=5)return false;// 不在6的倍数两侧的一定不是素数
    for(int i=5;i<=(int)sqrt(n);i+=6)
    {
    // 判断是否是 5,7，11,13的倍数
        if(n%i==0 || n%(i+2)==0)return false;
    }
    return true;
}
int prime[maxn],pNum=0;// 存储素数表，后面需要重复使用
void findPrime()
{
    for(int i=1;i<maxn;i++)
    {
        if(isPrime(i))
        {
            prime[pNum++]=i;
        }
    }
}
// 使用结构体存储素因子
struct factor
{
    int x,cnt;// 素因子、个数
}fac[10];// long int 范围的数的素因子在10个以内
int main()
{
    findPrime();// 调用函数求素数表
    int n,num=0;
    cin>>n;
    // 1和素数需要特判
    if(n==1)printf("1=1");
    else if(isPrime(n))
    {
        cout<<n<<"="<<n;
    }
    else
    {
        printf("%d=",n);
        int temp=(int)sqrt(n);
        for(int i=0;i<pNum&&prime[i]<=temp;i++)
        {
            if(n%prime[i]==0)
            {
                fac[num].x=prime[i];
                fac[num].cnt=0;// 只有一个时，让次数为0，即不显示
                while(n%prime[i]==0)
                {
                    fac[num].cnt++;// 次数+1
                    n/=prime[i];
                }
                num++;
            }
        }
        for(int i=0;i<num;i++)
        {
            if(i>0)printf("*");// 第一个前面无符号
            printf("%d",fac[i].x);
            if(fac[i].cnt>1)
            {
                printf("^%d",fac[i].cnt);
            }
        }
    }
    return 0;
}