C++

$\color{#cc33ff}{— > 算法基础课题解}$

朴素筛:

$时间复杂度： O(nlogn)$

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];

void get_primes(int n) { // 朴素筛
    for (int i = 2; i <= n; i ++) {
        if (!st[i])
        primes[cnt ++] = n; // 等于几都可以，求的是素数的个数
        for (int j = i + i; j <= n; j += i) st[j] = true; 
    }
}

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

    get_primes(n);
    cout << cnt;
    return 0;
}

埃式筛:

$时间复杂度： O(nloglogn)$

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];

void get_primes(int n) { // 埃式筛
    for (int i = 2; i <= n; i ++) {
        if (!st[i]) {
            primes[cnt ++] = n; // 等于几都可以，求的是素数的个数
            for (int j = i + i; j <= n; j += i) st[j] = true; 
        }
    }
}

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

    get_primes(n);
    cout << cnt;
    return 0;
}

线性筛:

$时间复杂度： O(n)$

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6 + 10;

int primes[N], cnt;
bool st[N];

void get_primes(int n) { // 线性筛
    for (int i = 2; i <= n; i ++) {
        if (!st[i]) primes[cnt ++] = i;

        for (int j = 0; primes[j] <= n / i; j ++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break; // primes[j]一定是i的最小质因子
        }
    }
}

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

    get_primes(n);
    cout << cnt;
    return 0;
}