話說小弟做這題不知為何一直都是TLE...

小弟先來說說我解這題的邏輯好了--給出正整數x->檢查所有正整數a<=sqrt(x)是否整除x(另外注意x==1的情況).

--但只要知道這題的時限是"2s"的話, 就能肯定以上方法肯定會TLE了.

所以小弟將邏輯換成: 給出正整數x->檢查x是否2的倍數->檢查所有正奇數a<=sqrt(x)是否整除x(另外注意x==1, x==2的情況).

--這大概是目前大部分解題者的邏輯, 但小弟依照這個邏輯所寫的程式碼還是TLE.(程式碼如下)

/**********************************************************************************/
/*  Problem: a007 "判斷質數"                                                  */
/*  Language: CPP (743 Bytes)                                                     */
/*  Result: TLE(2s) judge by this@ZeroJudge                                       */
/*  Author: yinz at 2013-01-25 20:07:29                                           */
/**********************************************************************************/


#include <cmath>
#include <iostream>
using namespace std;
int main()
{
     int i,x;
     bool b;
     while(cin>>x)
     {
          b=true;
          if (x==2)
          {
               cout<<"質數"<<endl;
               continue;
          }
          else if (x%2==0)
          {
               cout<<"非質數"<<endl;
               continue;
          }
          
          for (i=3; i<=sqrt(x); i+=2)
          {
               if (x%i==0&&x!=i)
               {
                    b=false;
                    break;
               }
          }
          if (b==true)
               cout<<"質數"<<endl;
          else
               cout<<"非質數"<<endl;
     }
     return 0;
}

小弟由於不知TLE的原因, 所以在程式碼上動了不少省時(可能會省時)的部分, 但結果依舊是TLE.

故此小弟又在邏輯上動手腳:  給出正整數x->檢查x是否2或3的倍數->檢查所有a≡±1(mod6)[由於所有a≡0,±2,3(mod6)都是2或3的倍數]且a<=sqrt(x)是否整除x(另外注意x==1, x==2, x==3的情況).

--這樣的話對於所給出的正整數x, 最多只需要執行((sqrt(x)/3)+2)次餘除法運算便可得知是否質數. (程式碼如下)

 /**********************************************************************************/
/*  Problem: a007 "判斷質數"                                                  */
/*  Language: CPP (786 Bytes)                                                     */
/*  Result: TLE(2s) judge by this@ZeroJudge                                       */
/*  Author: yinz at 2013-08-05 20:18:44                                           */
/**********************************************************************************/


#include<iostream>
#include<math.h>
using namespace std;
main()
{
    int x;
    int b;
    while(cin>>x)
    {
        b=1;
        if(x==2||x==3)
        {
            cout<<"質數"<<endl;
            continue;
        }
        else if(x==1 || x%2==0||x%3==0)
        {
            cout<<"非質數"<<endl;
            continue;
        }
        double a=sqrt(x);
        for(int i=5;i<=a;i+=6)
        {
            if(x%i==0)
            {
                b=0;
                break;
            }
            if(x%(i+2)==0)
            {
                b=0;
                break;
            }
        }
        if(b)
        {
            cout<<"質數"<<endl;
        }
        else
        {
            cout<<"非質數"<<endl;
        }
    }
return 0;
}

但正如各位所見, 還是TLE...... 

小弟在此懇請高手賜教, 感激不盡.