求小于n的所有素数的数量。

多组输入，输入整数n(n<1000000），以0结束。

输出n以内所有素数的个数。

10

0

4

	int f[1000004];

	int i, j;

	memset(f, 0, sizeof(f));

    f[1]=1 ;  //标记1的不是素数  标记0的是素数

	i=2;

	while(i<=500000) //这个地方需要优化

	{

		for(j=i*2; j<=1000000; j+=i )

		{

			f[j]=1;

		}

		i++;

		while(f[i]==1)

		{

			i++;

		}

	}

int f[100000000];

//优化素数筛 筛1百万以内的素数

int main()

{

    int i, j;

    f[1]=1;

    memset(f, 0, sizeof(f));

    int dd=sqrt(1e8+0.5);

    i=2;

    while(i<=dd)

    {

        for(j=i*2; j<=1000000; j+=i)

            f[j]=1; //标记不是素数

        i++;

        while(f[i]==1)

            i++; //移动到下一个是素数的地方

    }

    //下标从2开始，f[i]=1表示不是素数，f[i]=0是素数

bool f[N+1]; //标记数组

int num=1; //控制素数表下表

int su[100000]; //素数标

void Oula_shai()  //欧拉素数筛法

{

    int i, j;

    memset(f, true, sizeof(f)); //初始化假设每个数都是素数

    for(i=2; i<=N; i++) //从2开始测试

    {

        if(f[i]==true)

            su[num++]=i; //将该数存入素数表

        for(j=1; j<num; j++) //遍历整个素数表

        {

            if(i*su[j]>N) //如果超出了最大上界 跳出

                break;

            f[i*su[j]]=false; //将倍数从素数筛里筛除

            if(i%su[j]==0) //若当前素数是i的最小素因子，则分析下一个整数

                break;

        }

    }

}  //注意由于初始化，f[0]和f[1]都是true, 但0和1既不是素数也不是合数

#include <stdio.h>

#include <string.h>

#include <math.h>

#define N 1000000

bool f[N+1];

int num=1;

int su[100000];

void Oula_shai()

{

    int i, j;

    memset(f, true, sizeof(f));

    for(i=2; i<=N; i++)

    {

        if(f[i]==true)

            su[num++]=i;

        for(j=1; j<num; j++)

        {

            if(i*su[j]>N)

                break;

            f[i*su[j]]=false;

            if(i%su[j]==0)

                break;

        }

    }

}

int main()

{

    int n;

    Oula_shai();

    while(scanf("%d", &n)&&n)

    {

        int ans=0;

        for(int i=1; i<num; i++)

        {

            if(su[i]<=n)

                ans++;

            else

                break;

        }

        printf("%d\n", ans );

    }

    return 0;

}