输入包含多个测试实例,每个实例包含两行,第一行为整数n,第二行有n个整数(每个整数长度不超过32位,并且每个整数不小于2)。
输出素数的个数。
样例输入:
3
2 3 4
样例输出:
2
这是我写的代码,输入小数据的时候没有问题,数一大就不行了,(因为math.h库里的函数sqrt精度不够,所以又写了一个求平方根函数)。
我听别人说这个题可以用线性筛法写,但我看线性筛法是求一个范围内所有素数的算法呀,跟这题的意思好像不一样,也就没有去用。
这个代码是哪里错了可以改进,还是可以用其他的方法去做,求高人指点!!
#include<stdio.h>
long long int msqrt(long long int n)//求平方根
{
long long int i=0;
while(1)
{
if(i*i<=n)
i++;
else
return i-1;
}
}
long long int prime(long long int n)
{
if(n==0)
return 0;
if(n==1)
return 0;
if(n==2)
return 1;
if(n==4)
return 0;
long long int i;
for(i=2;i<msqrt(n);i++)
{
if(n%i==0)
return 0;
}
return 1;
}
int main()
{
long long int x,i,n;
while(scanf("%lld",&n)!=EOF)
{
i=0;
while(n--)
{
scanf("%lld",&x);
if(prime(x))
i++;
}
printf("%lld",i);
}
return 0;
}