我是最近開始學習程式語言，但一下就被這題卡住了...
不管怎麼試都一直逾時，於是到討論區爬文，但是...有夠亂 = ='' ，都不註記是哪種程式語言，找C語言找的好累!
最後寫出2種方法，仍逾時，只好發文求救了

第一種

#include<stdio.h>

#include<math.h>

int main(void)

{

    int a,b,i,s;                          /*a是輸入的數，b是餘數，s=√a*/

    while(scanf("%d",&a)!=EOF)

    {

    s=sqrt(a);

    for(i=2;i<=s+1;i++)             /*檢查除以2~√a的餘數*/

    {

          b=a%i;

          if(b==0)

          break;

    }

    if(b==0)

    printf("非質數\n");

    if(b!=0)

    printf("質數\n"); 

    } 

    return 0;

}  

第二種  先檢驗是否為2或3的倍數，如果不是，只需檢查6n+1及6n+5

#include<stdio.h>

#include<math.h>

int main(void)

{

    int a,jud=0,con,con2=0;       /*a是輸入的數，jud=0是質數，jud=1非質數，con是除數，con2讓con一次+4一次+2 */

    while(scanf("%d",&a)!=EOF){

    if(a%2==0)

    jud=1;

    if(a%3==0)

    jud=1;

    if(a==2||a==3)

    jud=0;

    for(con=5;con<=sqrt(a)&&jud==0;)

    {

         if(a%con==0)

         jud=1;

         if(con2==0)

         {

          con+=2;

          con2++;

         }

         if(con2==1)

         {

          con+=4;

          con2--;

         }

    }

    if(jud==0)

    printf("質數\n");

    else

    printf("非質數\n");

    jud=0;

}

    return 0;

}  

希望有人可以給點建議，再簡化程式 

至於討論區中有些人建議的"建表"還沒學過，也可提供學習資源給我

建表...其實就是用篩法

速度很快

http://zh.wikipedia.org/zh-tw/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95

可以只建到46340

然後只和小於46340的質數試除判斷 (若一數可被合數整除,則亦可被此合數之質因數整除)