高中生程式解題系統：d709: 判断质数（一）

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結 https://zerojudge.tw/ShowProblem?problemid=d709。

想法是：「目前要判斷的整數 N，用已知的質數 prime 去除。」

程式碼：

#include <stdio.h>
#include <cmath>

using namespace std;

const long long int limitValue = 1000000;

const int num = 78500;

bool primeFlag[limitValue + 1];

int prime[num+1] = {2, 3, 5, 7, 11, 13};
int cnt = 0;

void genPrimeArray()
{
    int index = 6;

    for(int i = 0; i < index; i++)
        primeFlag[prime[i]] = 1;

 bool isPrime;
 for(int i = 15; i <= limitValue; i += 2)
 {
  isPrime = true;
  int k = 1;
  int terminal = sqrt(i);
  for(int c = prime[k]; c <= terminal; k++, c = prime[k])
  {
   if( i % c == 0)
   {
    isPrime = false;
    break;
   }
  }

  if(isPrime == true)
  {
   prime[index] = i;
   primeFlag[prime[index]] = 1;
   index++;
  }
 }
}

int main(void) {
 genPrimeArray();

 int p ;
 while(scanf("%d",&p)&& p!=0){
  printf("%d\n", 1 - primeFlag[p]);
 }

 return 0;
}