---

請問一下這題到底是用什麼演算法才能0ms的,我蠻好奇的

 

我只有12ms,3.4MB,順便請幫我看看我程式碼能否在優化

#include<cstdlib>

#include<iostream>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

const int MAX=1000001;

const int Sqrt_MAX=1000;

vector<int>Prime;

bool P[MAX];

 

void Primer()

{

    int var,multi,val;

    P[0]=true;

    P[1]=true;

    for(var=2;var<=Sqrt_MAX;var++)

    {

        if(!P[var])

        {

            for(multi=(MAX-1)/var,val=multi*var;multi>=var;multi--,val-=var)

            {

                if(!P[multi])

                {

                    P[val]=true;

                }

            }

        }

    }

    for(var=2;var<MAX;var++)

    {

        if(!P[var])

        {

            Prime.push_back(var);

        }

    }

}

 

int main()

{

    Primer();

    int x,val;

    bool multi=false;

    vector<int>amount(Prime.size(),0);

    vector<int>Clear(Prime.size(),0);

    vector<int>::iterator ite,var;

    while(cin>>x)

    {

        if(!P[x])

        {

            cout<<x<<endl;

        }

        else

        {

             do

            {

                for(ite=Prime.begin(),var=amount.begin();(ite<Prime.end())&&((*ite<=x));ite++,var++)

                {

                    if(x%(*ite)==0)

                    {

                        (*var)+=1;

                        x/=(*ite);

                        break;  

                    }

                }

            }while(x!=1);

            for(ite=Prime.begin(),var=amount.begin();var<amount.end();var++,ite++)

            {

 

                if(*var>1)

                {

                    if(multi)

                    {

                        cout<<"* ";

                    }

                    cout<<*ite<<"^"<<*var<<" ";

                    multi=true;

                }

                else if(*var==1)

                {

                    if(multi)

                    {

                        cout<<"* ";

                    }

                    cout<<*ite<<" ";

                    multi=true;

                }

            }

            cout<<"\n";

            multi=false;

            amount=Clear;

        }

    } 

 

---

 

用像vector這種複雜的結構本來就很花時間，而且也沒必要那麼麻煩，因為它是電腦，要用它的邏輯解題，根本不用列出質數。

 

這是我的方法，參考一下:

 

#include<iostream>

using namespace std;

 

const int MAX_N = 1000000;

 

void solve(int num){

int if_first_time=0;

for (int i=2;i<MAX_N;i++){

int count = 0;

while (num%i == 0){

count++;

num/=i;

}

if (count){

if (if_first_time) cout << " *";

else if_first_time++;

}

if (count == 1) cout << " " << i;

else if (count > 1) cout << " " << i << "^" << count;

if (num == 1) break;

}

cout << endl;

}

 

int main(){

int n;

while(cin >> n) solve(n);

return 0;

}

 

---

其實我是被a007的題目影響了,所以說這題的測資不會像a007一樣大盜200000筆嗎?