没有优化的直观暴力

解法

1）素数筛
2）用递归写出能分解的最小的素数
能拥递归的前提:预知了递归的层数不会太大
原因：最小素数是2
假设是六位数的数，全是由于2来组成的，也就是我们最大的递归层数
由于2^10=1024
粗略估计，那么2^20约等于1000000
也就是说，最大递归不会超过20层。

AC代码

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

const int maxn=1000000+5;
bool tag[maxn]={0};

vector<int> aa;

void init()
{
    //0是素数 
    tag[0]=1;
    tag[1]=1;
    tag[2]=0;
    for(int i=2;i<500000+2;++i)
    {

        for(int j=2;i*j<1000000+4;++j)
        {
            tag[i*j]=1;
        }    
    } 

    for(int i=2;i<1000000+4;++i)
    {
        if(0==tag[i])
        {
            aa.push_back(i);
        }
    }
}


queue<int> q;

void rt(int n)
{
    for(int i=0;i<aa.size();++i)
    {
        if(1==n)
        {
            return ;
        }

        if(0==n%aa[i])
        {
            q.push(aa[i]);
            n/=aa[i];

            rt(n);
            return ;
        }
    }
}


int main()
{
    init();

    int n;
    while(~scanf("%d",&n))
    {
        while(!q.empty())
        {
            q.pop();
        }

        rt(n);

        printf("%d =",n);
        int len=q.size();
        for(int i=0;i<len;++i)
        {
            if(i==len-1)
            {
                printf(" %d\n",q.front());
                q.pop();
            }
            else
            {
                printf(" %d *",q.front());
                q.pop();
            }
        }
    }

    return 0;
}