题目链接:https://www.acwing.com/problem/content/description/870/
时/空限制：1s / 64MB

题目描述

给定一个正整数n，请你求出1~n中质数的个数。

输入格式

共一行，包含整数n。

输出格式

共一行，包含一个整数，表示1~n中质数的个数。

数据范围

1≤n≤10^6

输入样例

8

输出样例

4

解题思路

题意:求出1~n中质数的个数。
思路:利用筛法就行了，朴素筛法、埃筛和线性筛都可以。

Accepted Code:

//朴素筛
/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
bool isp[MAXN];
int get_prime(int n) {
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!isp[i])
            cnt++;
        for (int j = i << 1; j <= n; j += i)
            isp[j] = true;
    }
    return cnt;
}
int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", get_prime(n));
    return 0;
}
//埃筛
/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
bool isp[MAXN];
int prime[MAXN];
int get_prime(int n) {
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!isp[i])
            prime[cnt++] = i;
        for (int j = 0; j < cnt && prime[j] <= n / i; j++) {
            isp[i * prime[j]] = true;
            if (!(i % prime[j]))
                break;
        }
    }
    return cnt;
}
int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", get_prime(n));
    return 0;
}
//线性筛
/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 5;
bool isp[MAXN];
int prime[MAXN];
int get_prime(int n) {
    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (!isp[i])
            prime[cnt++] = i;
        for (int j = 0; j < cnt && prime[j] <= n / i; j++) {
            isp[i * prime[j]] = true;
            if (!(i % prime[j]))
                break;
        }
    }
    return cnt;
}
int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", get_prime(n));
    return 0;
}