http://acm.hdu.


#include <stdio.h>
void abc();

int z[100000];
int main()
{
    int n,a,i;
    abc();
    while(scanf("%d",&n)!=EOF)
    {
        a=0;
        for(i=1;n>=z[i];i++)
        {
            if(n%z[i]==0)
                {a=i;}
        }
        printf("%d\n",a);
    }

    return 0;
}

void abc()
{
    int i,j,a=0,t;
    z[0]=1;z[1]=2;z[2]=3;z[3]=5;z[4]=7;z[5]=11;z[6]=13;z[7]=17;z[8]=19;
    t=4;
    for(i=23;i<1000000;i+=2)
    {
        for(j=2;j<=t;j++)
            {
                if(i%z[j]==0)
                {
                    a=0;break;
                }
                else
                    a=1;
            }
            if(a==1)
            {t++;z[t]=i;}
    }
}

for(i=0;i<sqrt(n);i++)
这样一来，函数既用来判断n/i是否素数，如果是素数则肯定是最大的，只需要再判断从1到该最大素数之间素数的个数并用函数返回即可；不是素数则返回-1.无需用数组。

[ 本帖最后由 wmf2014 于 2015-2-15 11:11 编辑 ]

可以帮忙打下你的思路吗，实在想不明白，麻烦了

如果不用数组的话怎么判断他到底是第几个素数呢？

使用了各种优化手段，传统方法无法满足acm速度要求。查找资料说需要用厄拉多塞筛法生成一张素数排位表，直接通过查表即可（厄拉多塞筛法见http://blog.），综合各方资料c代码如下(提交显示140ms，通过):

#include <stdio.h>
int a[1000000]={0};
void main()
{
    int i,j,n,k=1;
    for(i=2;i<1000000;i++)
    {
        if(a[i]==0)
        {
            a[i]=k;
            for(j=i+i;j<1000000;j+=i)a[j]=k;
            k++;
        }
    }
    while(scanf("%d",&n)!=EOF){printf("%d\n",a[n]);}
}

谢谢，我懂了