VIRTUALS

the virtual labs for the virtuals

0%

【AcWing算法基础】第四讲-数学知识-质数 AcWing 868. 筛质数

Posted on Edited on In , , , ,

摘要：
常见质数筛法。

题目

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

输入格式
共一行，包含整数 $n$。

输出格式
共一行，包含一个整数，表示 $1$∼$n$ 中质数的个数。

数据范围
$1≤n≤10^6$

输入样例：

8

输出样例：

4

朴素筛

从2开始枚举，依次将当前数的倍数（$2 * i, 3 * i, 4 * i … n$）标记为「非质数」，剩余的数就一定是质数。

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
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int pr[N];
bool st[N];
int cnt;

int main()
{
    int n;
    cin >> n;
    
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) pr[++cnt] = i;              // we consider i is a prime num if i wasn't get sieved
        for (int j = i + i; j <= n; j+=i)       // sieves all the multiple nums of i
        {
            st[j] = true;
        }
    }
    
    cout << cnt << endl;
    return 0;
    
}

埃氏筛

从2开始枚举，依次仅将质数的倍数标记为「非质数」，剩余的数一定是质数。

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
#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int pr[N];
bool st[N];
int cnt;

int main()
{
    int n;
    cin >> n;
    
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) 
        {
            pr[++cnt] = i;                          // we consider i is a prime num if i wasn't get sieved   
            for (int j = i + i; j <= n; j+=i)       // sieves all the multiple nums of i when i is a prime num
                st[j] = true;
        }
        
    }
    
    cout << cnt << endl;
    return 0;
    
}

线性筛

待更新。

原题链接： AcWing 868. 筛质数