杭电ACM-2138 (求素数 求素数!!!)

题目：

2138题

(●ˇ∀ˇ●)嘿嘿 看到这道题马上想到了打表，结果是懵逼的

打表代码（误）：

#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)
所以只能放弃打表了...用原始的方法
不过...超时是一定要考虑的

#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++)这是为了防止超时而设计的！！！