---

雖然說是成功,也用到建表,但看了很多文章,還是覺得自己的程式碼可以再更快,請問有高手能幫忙看一下嗎,小弟還是剛學一個學期程式的菜鳥

秒數1.8s 572KB

 

#include<iostream>

#include<vector>

using namespace std;

//46341是2147483647的根號

const int MAX=46341;

vector<int>Primer;

 

void isPrime()

{

    unsigned var,val,multi;

    vector<bool>Prime(MAX);

//216是46340的根號 

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

    {

        if(!Prime[var])

        {

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

            {

                if(!Prime[multi])

                {

                    Prime[val]=true;

                }

            }

        }

    }

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

    {

        if(!Prime[var])

        {

            Primer.push_back(var);

        }

    }

}

 

int main()

{

    int count=0,var;

    vector<int>::iterator ite;

    isPrime();

    int x;

    while(cin>>x)

    {  

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

        {

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

            {

                count++;

                cout<<"非質數"<<endl; 

                break;

            }

        }

        if(count==0)

        {

            cout<<"質數"<<endl; 

        }

        count=0;

    }

    return 0;

} 

 

---

 

---

 

因為這題時間吃很重,所以我就先自己算了XD

 

vector 我也是剛學的 ,書上說他是一個template,我只知道這麼多了 

 

---

vector是一個動態陣列 
vector的空間隨著你加入的東西而變大 
可以節省不必要的空間(應該吧)