筛质数

线性筛 $O(n)$

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;
int primes[N];
bool mystate[N];//记录是否为合数，是为true

int cntPrime(int n)
{
    int cnt = 0;
    for (int i = 2; i <= n; ++i)
    {
        if (!mystate[i])
            primes[++cnt] = i;
        for (int j = 1; primes[j] <= n / i; ++j)
        {
            mystate[primes[j] * i] = true;//这里思路要注意，线性筛是用每个合数的最小质因数将其筛去，且每一个数只判断一次
            if (i % primes[j] == 0)//因此这个条件不成立时，说明此时的primes[j]还不是i的最小质因数，但是是primes[j]*i的最小质因数，这样保证不重复也不遗漏
                break;
        }
    }
    return cnt;
}

int main()
{
    int n;
    cin >> n;
    memset(mystate, false, sizeof(mystate));
    memset(primes, 0, sizeof(primes));
    printf("%d", cntPrime(n));
    return 0;
}

埃氏筛 $O(nlogn)$

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;
int primes[N];
bool mystate[N];//记录是否为合数，是为true

int cntPrime(int n)
{
    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (!mystate[i])
        {
            primes[++cnt] = i;
            for (int j = i + i; j <= n; j += i)//2i,3i,4i,...
                mystate[j] = true;
        }
    }
    return cnt;
}

int main()
{
    int n;
    cin >> n;
    memset(mystate, false, sizeof(mystate));
    memset(primes, 0, sizeof(primes));
    printf("%d", cntPrime(n));
    return 0;
}