P2T a007判斷質數

方法一： 判斷是否被  2 ~ 根號n 整除 ， 但在 zerojudge的 a007仍會 TLE
    1 算出 q = int(sqrt(n))
    2 for i=2 ~ q ，若 n 被 i 整除則非質數
    3  i ~ q 皆不整除就是質數

方法二：先建一個質數表pr 再判斷是否被 2 ~ q 之內的質數整除 {大約會快10倍}
     (一)建 2~46340之間的質數表，共有4792個質數，最小是2、最大是 46337
           vector <int> pr;
     pr.push_back(2);           // 2 是質數，直接加入 pr
     for( i=3; i<=46340; i+=2 )  // 只判斷奇數是否為質數
     {
        q = int( sqrt(i) );
        bool y = 1;   //以下 判斷 i 是否被質數表中的質數整除
        for(j=0; y && j<pr.size() && pr[j]<=q ; ++j)
              if( i % pr[j] == 0 ) y=0;
        if( y ) pr.push_back(i);   // i 也是質數
     }
    註：vector<資料型別 > 可說是記憶空間動態調整的陣列
            不需 int pr[ 須先宣告大小 ]; 當有新資料時 pr.push_back( 新資料 );
            總共有幾個元素可由 pr.size() 的值查詢

     (二) 每輸入的 n 只檢查 2~q 中的質數是否可整除 n 可加快速度
           while( cin >> n ) //有  20 萬筆 n
     {
        q = int( sqrt(n) );
        bool y = 1;   //以下 判斷 n 是否被質數表中的質數整除
        for(j=0; y && j<pr.size() && pr[j]<=q ; ++j)
              if( n % pr[j] == 0 ) y=0;
        if( y ) cout << "質數\n";  // 印出質數
        else  cout << "非質數\n";  // 印出非質數
     }

I/O 加速： cin,cout 會比 scanf,printf慢，可改為如下
        while( scanf("%d", &n)==1 ) //有  20 萬筆 n
    {
       …
       if( y ) printf("質數\n");  
       else  printf("非質數\n");    
    }