欧拉筛找素数

任何合数都可以表示为多个素数的乘积，合数肯定有一个最小的质因子，通过这个最小质因子筛掉合数，保留素数。

题目：求小于或等于n的素数个数

 

Write a program which reads an integer n and prints the number of prime numbers which are less than or equal to n. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5 and 7.

 

Input

 

Input consists of several datasets. Each dataset has an integer n (1 ≤ n ≤ 999,999) in a line.

 

The number of datasets is less than or equal to 30.

 

Output

 

For each dataset, prints the number of prime numbers.

 

Sample Input

 

10
3
11

 

Output for the Sample Input

 

4
2
5
代码：

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<cstring>
using namespace std;
const int maxa=1000010;
int prime[maxa];
bool flag[maxa];
int cnt,n;

void find_prime()
{
        cnt=0;
        memset(flag,true,sizeof(flag));
        flag[0]=flag[1]=false;
        for(int i=2;i<=n;i++)
        {
            if(flag[i])
                prime[cnt++]=i;
            for(int j=0; j<cnt&&prime[j]*i<=n; j++)
            {
                flag[i*prime[j]]=false;　　　///如果n足够大，每次最少筛一个
                if(i%prime[j]==0) break;    ///prime[j]必定是prime[j]*i和i的最小质因子
            ///比如i=4，筛掉8之后就停止了，不会筛4*3=12，12留给i=6的时候去筛，当i=6时，筛掉12，不会筛i*3=18，留给i=9的时候去筛
            ///i=9时，筛掉18之后，再筛掉27，不会筛5*9=45，45留给i=15去筛，i=15时，筛掉30和45，不会筛掉75，75留给i=25筛
            ///很明显，是通过最小质因数来筛掉合数的，而且保证不会重复筛，降低了时间复杂度
            }
        }
        cout<<cnt<<endl;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        find_prime();
    }
}

/*
模拟欧拉筛：
判断25以内的素数
数字 1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23  24   25
判断 f           f       f       f   f    f         f         f    f    f        f          f    f   f        f       f
i=2;i<=25;    yes;prime[0]=2;cnt=1;
for
j=0;j<1 && 2*2<=25;        flag[4]=false; if(2%prime[0]==0) yes break;
j=1;j<1 && no

i=3;i<=25;  yes;prime[1]=3;cnt=2;
for
j=0;j<2 && 2*3<=25;        flag[6]=false; if(3%prime[0]==0) no
j=1;j<2 && 3*3<=25;        flag[9]=false; if(3%prime[1]==0) yes break;

i=4;i<=25;  no;
for
j=0;j<2 && 2*4<=25;        flag[8]=false; if(4%prime[0]==0) yes break;

i=5;i<=25;  yes;prime[2]=5;cnt=3;
for
j=0;j<3 && 2*5<=25;        flag[10]=false; if(5%prime[0]==0) no
j=1;j<3 && 3*5<=25;        flag[15]=false;    if(5%prime[1]==0) no
j=2;j<3 && 5*5<=25;        flag[25]=false; if(5%prime[2]==0) yes break;

i=6;i<=25;  no;
for
j=0;j<3 && 2*6<=25;        flag[12]=false; if(6%prime[0]==0) yes;break;

i=7;i<=25;    yes;prime[3]=7;cnt=4
for
j=0;j<4 && 2*7<=25;        flag[14]=false;    if(7%prime[0]==0) no
j=1;j<4 && 3*7<=25;        flag[21]=false;    if(7%prime[1]==0) no
j=2;j<4 && 5*7=35;break;

i=8;i<=25;    no
for
j=0;j<4 && 2*8<=25;        flag[16]=false;    if(8%prime[0]==0) yes;break;

i=9;i<=25;    no
for
j=0;j<4 && 2*9<=25;        flag[18]=false;    if(9%prime[0]==0) no;
j=1;j<4 && 3*9=27;break;

i=10;i<=25; no
for
j=0;j<4 && 2*10<=25;    flag[20]=false; if(10%prime[0]==0) yes;break;

i=11;i<=25; yes;prime[4]=11;cnt=5
for
j=0;j<5 && 2*11<=25;    flag[22]=false;    if(11%prime[0]==0) no
j=1;j<5 && 3*11=33;break;

i=12;i<=25; no;
for
j=0;j<5 && 2*12<=25;    flag[24]=false;    if(12%prime[0]==0) yes;break;

i=13;i<=25; yes;prime[5]=13;cnt=6
for
j=0;j<6 && 2*13=26 break;

i=14;no
for
break;

i=15;no
for
break;

i=16;no
for
break;

i=17; yesprime[6]=17;cnt=7
for
break;

i=18;no
for
break;

i=19; yes; prime[7]=19,cnt=8
for
break;

i=20; no
for
break;

i=21; no
for
break;

i=22; no
for
break;

i=23; yes; prime[8]=23;cnt=9
for
break;

i=24;no
for
break;

i=25;no
for
break;
*/