TLE耶 有更快的寫法嗎?  感謝...

#include  
#include   
int main() {  
     int n,i;  
     while( scanf("%d",&n)!=EOF ){
     if(n<=1)printf("1\n");
                 if(n==2) printf("0\n");  
             for(i=2;i
                if(n%i==0){
     printf("1\n");  
                           break;
    }  
                if(i>sqrt((double)n)-1){
     printf("0\n");  
                           break;
    } 
    }  
  } 
    return 0;  
}

建質數表

我大致上可以給你一個方向是

假設你確定 a 是質數

則 a 的倍數必不為質數

如此你只需要檢查 sqrt(MAX) 內的質數 便能確定MAX內所有的質數

細部有不少值得思考 加速的空間

不過只要有這個觀念的程式 就會AC 

建質數表

我大致上可以給你一個方向是

假設你確定 a 是質數

則 a 的倍數必不為質數

如此你只需要檢查 sqrt(MAX) 內的質數 便能確定MAX內所有的質數

細部有不少值得思考 加速的空間

不過只要有這個觀念的程式 就會AC 

我只会这样的质数表

/**********************************************************************************/

/*  Problem: d709 "判断质数（一）" from 判断质数系列                 */

/*  Language: CPP (198 Bytes)                                                     */

/*  Result: AC(0.2s, 4.1MB) judge by this@ZeroJudge                               */

/*  Author: a450 at 2013-10-13 10:27:09                                           */

/**********************************************************************************/

#include

int p[1000001], n;

main(){

p[1]=1;

for(int i=2; i*i<=1000000; i++) if(!p[i]) for(int j=i*2; j<=1000000; j+=i) p[j]=1;

while(scanf("%d", &n)==1&&n) printf("%d\n", p[n]);

}