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
26
27
28
29
30
31
#include <cstdio>
const int MaxPrimeNum = 78499, MaxSize = 1000001;
int MinPrime[MaxSize], prime[MaxPrimeNum], i = 2, j, len, num_prime = 1, tmp, n;
void euler_sieve(int &n)
{
    prime[num_prime++] = i;
    for (i = 3; i <= n; i += 2)
    {
        if (!MinPrime[i])
        {
            prime[len = num_prime++] = i;
        }
        else
        {
            len = MinPrime[i];
        }
        for (j = 2; j <= len; ++j)
        {
            if ((tmp = i * prime[j]) > n)
            {
                break;
            }
            MinPrime[tmp] = j;
        }
    }
    printf("%d\t", num_prime - 1);
}
int main()
{
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX