(Zj) a007: 判斷質數

如果數字<10000000，用表格

要不然，用sqrt(n)算法

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>
#include <cmath>
using namespace std;
int prime[10000001];
int check_prime[4793];
void build_form()
{
memset(prime,0,sizeof(prime));
//memset(check_prime,0,sizeof(check_prime));
prime[0]=prime[1]=1;
int n=0; //check+prime 用
for (int a=2;46350>a;a++)
{
if (prime[a]==0) //a-->prime
{
if (a>3162) //a^2>400000000
{
;
}
else
{
for (int b=a;10000000>=a*b;b++) prime[a*b]=1;
}
check_prime[n]=a;
n++;
}
}
}
int main ()
{
build_form();
int x;
while (scanf("%d",&x)!=EOF)
{
if (x<=10000000)
{
if (prime[x]==0) puts("質數");
else puts("非質數");
}
else
{
int check=0 , temp=sqrt(x);
for (int y=0;temp>=check_prime[y];y++)
{
if (x%check_prime[y]==0)
{
check=1;
break;
}
}
if (check==1) puts("非質數");
else puts("質數");
}
}
}