LFsWang--隨心所欲~~

檢驗質數算是寫C++中一件好玩又痛苦的事情吧~

在此分享我自己寫的檢測程式~給大家參考

此程式運行速率執行過你就知道了，給大家我的想法

首先，為了避免重複的計算，要先建立一個質數表作快取之用，而要做到多少呢?

此程式檢測範圍到2^31-1，而要檢測2^31-1是不是質數的最快方法是用√(2^31-1)以下的質數(約46341)一個一個來除(在此程式取50000以下的質數)，因此我們需要50000以下的質數表，而如何最快的建立50000以下的質數表呢?

首先由0 1 2 3 ......照順序，先排除1,0非質數，然後遇到的下一個數"2"，將它本身標記為質數，其倍數(4,6,8,10...)標記為合數！以此類推~下一個數字是3，將3標記為質數，其倍數標記為合數，然後下一個是4，不過4剛剛已經在檢查2的倍數中被標記為合數了，因此略過不檢查......

如果你聽不懂以上步驟，可以看看本人製作的圖片，其中的變化來了解其中的意思~~

===========================

//LFsWang 2011 CSJH980510
#include <iostream>


using namespace std;
bool p[50001];
int a,x,m;


inline void yn()
{
       for(x=0;x<50001;x++)
       {
                       if(p[x]&&(a%x==0&&a!=x))
                       {
                                       cout<<"非質數";
                                       return;
                        }
        }
        cout<<"質數";
}
             


int main()
{
    for(x=0;x<50001;x++)
    {
                        p[x]=true; 
    } 
    p[0]=false;
    p[1]=false;
    for(x=0;x<=250;x++)
    {
                       if(p[x])
                       {
                               m=2;
                               do
                               {
                                   p[x*m]=false;
                                   m++; 
                               }while(x*m<50001);
                               p[x]=true; 
                        }                       
    }
    while(cin>>a)
    {
                 yn();
                 cout<<endl; 
    } 
    return 0;
}