感觉这么简单的东西没必要讲的……
例题传送门= ̄ω ̄=

最直接的就是for(int i=2;i<=n;i++)判断i是否是n的质因数,然后递归……
其实只要做个小小小小小小小的优化就可以优化到√n,复杂度小好多啊!怎么做呢?
这样不就行了:for(int i=2;i*i<n;i++)

例题题解代码:

#include <iostream>
using namespace std;
inline void work(int num,int cnt)
{
    for(int i=cnt;i*i<=num;i++)
        if(num%i==0){cout<<i<<'*',work(num/i,i);return;}
    cout<<num;
}
int main()
{
    ios::sync_with_stdio(0);
    int n;cin>>n,cout<<n<<'=',work(n,2);
    return 0;
}


分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *