判断素数,在主涵数中调用涵数

要高效的判断素数的算法吗?

下面的在主函数中调用了

#include<stdio.h>
#include<math.h>
#define N 100000
int a[50000]={2};
int m;
void init()
{
int i,j,k=1,sure=1;
for(j=3;j<N;j++)
{
for(i=2;i<=sqrt(j);i++)
if(j%i==0)
{
sure=0;
break;
}
if(sure)
a[k++]=j;
sure=1;
}
m=k-1;
}

int prime(long n) //判断该数是否为素数
{
int i;
if(n<2)
return 0;
if(n==2)
return 1;
for(i=0;i<m;i++)
{
if(a[i]>sqrt(n))
break;
if(n%a[i]==0)
return 0;
}
return 1;
}

int main()
{
int a;
scanf("%d",&a);
init();
if(prime(a))//主函数中调用PRIME
printf("%d是素数\n",a);
else
printf("%d不是素数\n",a);
return 0;
}

看我的博客<