AOJ 0009 Prime Number 题解 《挑战程序设计竞赛》 � 码农场

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009

Prime Number

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, 7.

Output

For each dataset, prints the number of prime numbers.

http://www.hankcs.com/program/cpp/aoj-0009-prime-number.html
n以内的素数个数：……
2.6 数学问题的解题窍门
素数
艾氏筛法就行了

int  prime[MAX_N];            // 第i个素数

bool is_prime[MAX_N + 1];    //is_prime[i]为真的时候表示i为素数

int sieve(const int& n)

{

    int p = 0;

    fill(is_prime, is_prime + n + 1, true);

    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= n; ++i)

    {

        if (is_prime[i])

        {

            prime[p++] = i;

            for (int j = 2 * i; j <= n; j += i)

            {

                is_prime[j] = false;

            }

        }

    }

    return p;

}

Read full article from AOJ 0009 Prime Number 题解 《挑战程序设计竞赛》 � 码农场