You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

4.9 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 868. 筛质数

一、题目描述

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

输入格式 共一行,包含整数 n

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

数据范围 1≤n≤10^6

输入样例:

8

输出样例:

4

二、埃氏筛法

原理解析

先去掉2的倍数,再去掉3的倍数,再去掉4的倍数,……依此类推,最后剩下的就是素数。

如求100以内的素数,我们只要到去掉sqrt(100)的倍数就可以了,这是因为102倍已经被2的倍数去掉了,103倍已经被3的倍数去掉了,所以到10的时候只剩下1010倍以上的素数还存在。

同样的原因,我们在去掉3的倍数的时候,只要从3的3倍开始去掉就好了因为32倍已经被2的倍数去掉了。

QQ截图20210225151603.png

实现代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;
int primes[N], cnt; // primes[]存储所有素数
int st[N];          // st[x]存储x是否被筛掉
// 埃拉筛
void get_primes(int n) {
    for (int i = 2; i <= n; i++)
        if (!st[i]) {
            primes[cnt++] = i; // 记录素数
            for (int j = 2 * i; j <= n; j += i)
                st[j] = 1; // 成倍数的标识
        }
}

int main() {
    int n;
    cin >> n;
    get_primes(n);
    printf("%d\n", cnt);
    return 0;
}

三、欧拉筛

  • 不用每次筛去后剩下的能确定是素数中最大的数作为操作主体(在埃拉托色尼筛法中用235…),而是用已经晒出来的质数数组中的数作为操作主体

  • 核心思想:在埃氏筛法的基础上,让每个合数只被它的最小质因子筛选一次,以达到不重复的目的。

原理

1、每个合数都会被筛去

证明:n 为合数,设其质因子分解为 \LARGE n = p_1 \times p_2\times ...\times p_q$,其中\large p_i$可以等于\large p_j , \large p_1 为最小的素数

由于任意小于 p_1 的质数都不能整除 p_2 \times ... \times p_q,所以 n 会在遇到primes[j]=p_1时,也就是 \large i = p_2 \times ...\times p_q 时被筛去。

证毕,总结:就是枚举最小的质数因数

2、每个合数只会被筛去1

反证法: 设合数 n 即被 质数\large p_1 筛去,也被 质数\large p_{2} 筛去。那么有 \large n = q_1 \times p_1 = q_2 \times p_2,其中 p_1p_2 均是 n 的素因子。

不妨设 \large p_1 < p_2,则有q_1>q_2,且p_1 和 p_2 互素,故有 \large p_1 | q_2,也就是\large q_2 \% p_1=0

i 枚举到 q_2 时,质数数组是由小到大的,当遍历到 p_1 时,有 i \% p_1 == 0,此时跳出循环,不会再遍历到后面的 p_2

n 不会被 p_2 筛去,只会被其最小的素因子 p_1 筛去。

证毕

步骤

  • i=2 开始,如果 i 还没有被筛掉,则将 i 加入至素数列表中
  • 遍历当前素数列表primes[]筛去 i \times primes[j] (保证primes[j]*i不能越界,因为越界了对结果没意义。即i*primes[j]<=n)
  • 当遍历到能整除 i 的素数 primes[j] 时,筛去 i \times primes[j]停止对素数列表的遍历
  • 重复 2, 3, 4,直到所有不超过 n 的整数都被遍历过

素数列表中的元素即为所求的不超过 n 的所有素数

实现代码

#include <bits/stdc++.h>

using namespace std;

// 欧拉筛
const int N = 1e6 + 10;
int primes[N], cnt; // primes[]存储所有素数
int st[N];          // st[x]存储x是否被筛掉

void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) { // 捋着质数数组来
            st[primes[j] * i] = 1;                 // 质数因子的i倍被干掉
            if (i % primes[j] == 0) break;         // 只被它的最小质因子筛选一次
        }
    }
}

int main() {
    int n;
    cin >> n;
    get_primes(n);
    printf("%d\n", cnt);
    return 0;
}

五、练习题

洛谷 P3912 素数个数