C++進階研習：a007判斷質數

7/23 + 7/30  解 zerojudge.tw 中之 a007 判斷質數

#include <iostream>

#include <cstring>

#include <vector>

#include <cmath>

#define maxn 46340

using namespace std;

bool c[maxn+10];

vector <int> p;

// 以下 isp 為函式， 傳入 n 判斷是否為質數 

bool isp(int n)

{

  if(n<=maxn) return( !c[n] );

  int q = (int) sqrt(n);

  int k;

  for(k=0; k<p.size() && p[k]<=q ; ++k)

    if(n%p[k]==0) return false;

  return true;     

}

int main( )  // 主程式開始

{

  int i,j,k;

  memset(c,0,sizeof(c));    // 將 c 陣列全清為 0

  c[0]=c[1]=1;

  for(i=2;i<=maxn;++i)

  {

     if(c[i]==1) continue;   //非質數

     p.push_back(i);         // i是質數，放入 p 中 

     // 以下將是質數 i 的倍數 註記為非質數

     for(j=i+i; j<=maxn; j+=i)

       c[j]=1;                   

  }

  int n;

  while( cin >> n )   // 讀資料直到 EOF

  {

    if( isp(n) ) cout << "質數" << endl;

    else cout << "非質數" << endl; 

  }

  return 0;

}