題目：
2138題
(●ˇ?ˇ●)嘿嘿 看到這道題馬上想到了打表置尔，結(jié)果是懵逼的
打表代碼（誤）：
#include<stdio.h>
int a[10000000],i,j;
void init()
{
a[0]=1,a[1]=1;
for(i=2;i<5000000;i++)
{
for(j=i+i;j<5000000;j+=i)
{
if(a[j]==0)
a[j]=1;
}
}
}
int main()
{
init();
int n,k,m,cnt;
while(~scanf("%d",&n))
{
cnt=0;
for(k=0;k<n;k++)
{
scanf("%d",&m);
if(a[m]==0)
cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
OJ的顯示是：
Runtime Error (ACCESS_VIOLATION)
Runtime Error (ACCESS_VIOLATION)
Runtime Error (ACCESS_VIOLATION)
所以只能放棄打表了...用原始的方法
不過(guò)...超時(shí)是一定要考慮的
#include<stdio.h>
#include<math.h>
int main()
{
int n,a,k,i,cnt,flag;
while(~scanf("%d",&n))
{
cnt=0;
for(i=0;i<n;i++)
{
flag=0;
scanf("%d",&a);
for(k=2;k<=sqrt(a+0.0);k++)
{
if(a%k==0)
{
flag=1;
break;
}
}
if(flag==0)
{
cnt++;
}
}
printf("%d\n",cnt);
}
return 0;
}
注意：
for(k=2;k<=sqrt(a+0.0);k++)這是為了防止超時(shí)而設(shè)計(jì)的！＜穸唷牡昆！
