題目連結 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;
}
沒有留言:
張貼留言