#include <stdlib.h>     
#include <iostream>  
#include <string>  
#include <math.h>  
#include <iomanip>
#include <sstream>
#include <ctype.h>
#include <algorithm>
using namespace std;  

int main(void)     
{  
  int n,pr[100000],now=10;  
  pr[1]=2;  
  pr[2]=3;  
  pr[3]=5;  
  pr[4]=7;  
  pr[5]=11;  
  pr[6]=13;  
  pr[7]=17;  
  pr[8]=19;  
  pr[9]=23;  
  pr[10]=29;  
  pr[11]=31;  
  pr[12]=37;  
  pr[13]=41;  
  pr[14]=43;  
  pr[15]=47;  
  pr[16]=53;  
  pr[17]=59;  
  pr[18]=61;  
  pr[19]=67;  
  pr[20]=71;  
  pr[21]=73;  
  pr[22]=79;  
  pr[23]=83;  
  pr[24]=89;  
  pr[25]=97;  
  pr[26]=101;  
  pr[27]=103;  
  pr[28]=107;  
  pr[29]=109;  
  pr[30]=113;  
  while(cin>>n)  
  {  
    int pri=1,e=0;  
    for (int i=1;i<=now;i++)  
    {  
      if (n==pr[i]){e=1;break;}  
      if (fmod(n,pr[i])==0){pri=0;break;}  
    }  
    if (e==1){cout<<"yes\n";continue;}  
    else if (pri==0||sqrt(n)<pr[now]){cout<<"no\n";continue;}  
    else if (sqrt(n)>pr[now])  
    {  
      for (int i=pr[now]+1;i<sqrt(n);i++)  
      {  
        int pripri=1;  
        for (int j=1;j<=now;j++)  
        {  
          if (fmod(i,pr[j])==0){pripri=0;break;}  
        }  
        if (pripri==1){now++;pr[now]=i;}  
        if (fmod(n,pr[now])==0){pri=0;break;}  
      }  
      if (pri==0)cout<<"no\n";  
      else cout<<"yes\n";  
    }  
  }  
  return 0;     

}

這已經是我能想到最快的方法了Orz

嗯  你的ID長度可能會讓別人無法寄信給你

可以google一下 sieve method建立質數表的方式

6n+-1應該是sieve裡易懂好寫的方法之一