C++ 代码

### 线性筛
//重点理解：row-30
//这个 primes[j] <= n / i其实就是i*prime[j]<=n，变成除法应该是为了防止乘法溢出
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;

bool str[N];
int primes[N];

int prime(int n)
{
    int cnt = 0;

    for(int i = 2; i <= n; i++)
    {
        if(!str[i])
        {
            primes[cnt++] = i;
            // str[i] = true;
        }

        //这里的变界改为: j < cnt时 当j==cnt-1，primes[cnt-1] * i 可能>n,下面的str[primes[j]*i]就会越界！！
        //边界为 primes[j] <= n / i时，primes[j] * i <= n，下面的str不会越界发生段错误
        for(int j = 0; primes[j] <= n / i; j++)
        {
            str[primes[j] * i] = true;
            if(i % primes[j] == 0)
                break;
            //如果不break，有的数会被筛掉多次
            //例：i = 8， str[40 = 5 * 8] 被筛掉， 当 i= 20，str[40 = 2 * 20] 有多被筛掉一次
        }
    }
    return cnt;
}

int main()
{
    int n;
    cin >> n;

    int t = prime(n);
    cout << t;
}


### 朴素筛（埃氏筛）
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const  int N = 1e6 + 10;
bool str[N];

void is_prime(int n)
{
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(!str[i])
        {
            cnt ++;
            for(int j = i; j <= n; j += i)
                str[j] = true;
        }
    }

    cout <<cnt;
}


int main()
{
    int n;
    cin >> n;

    is_prime(n);

}