线性筛法解题

首先我们来看两种常用的质数筛

质数筛

判断 ~ 中哪些数是质数？

1. 埃氏筛

原理

已知一个数 的倍数都不是质数:

所以我们可以把一个数字 的倍数全部筛掉

for (int j = i + i; j <= n; j += i) st[j] = true;
// j == 2i
// j == 3i
// ··· ···
// j 会随着循环不断增加直到 j > n

首先开一个数组用来存放筛选出来的所有质数

const int N = 1000010;

int cnt; // 记录存的质数的个数
int primes[N]; // 存放质数的数组，默认全是质数 false

再用一个bool数组记录哪些数字被筛选了，st[i] == false代表 i 是质数

bool st[N]; // 默认全为 false

代码实现

void get_primes(int n) 
{
    for (int i = 2; i <= n; i++) // 遍历
    {
        if (st[i]) continue; // 如果 i 是合数，跳过下面语句
        primes[cnt++] = i; // 存储质数
        for (int j = i + i; j <= n; j += i) st[j] = true; // 埃氏筛
    }
}

2. 线性筛

原理

上面埃式筛法的缺陷在于，对于同一个合数，有可能被筛选多次，浪费效率

为了确保每一个合数只被筛选一次，线性筛用每个合数的最小质因子来筛

首先开一个数组用来存放筛选出来的所有质数，再用一个bool数组记录哪些数字被筛选了，st[i] == false代表 i 是质数

const int N = 1000010;

int cnt; // 记录存的质数的个数
int primes[N]; // 存放质数的数组，默认全是质数 false
bool st[N]; // 默认全为 false

循环 i 至 n ，然后每筛出一个质数，就存入 primes[] 数组里面，每次循环时 j 从头遍历 primes[] ,合数则为 primes[j] * i，直接筛掉

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;
    }
}

那么具体如何筛出合数能不重复筛呢？

我们已知在 筛选中， 与已知的所有比它小的质数相乘得到一个合数，并筛掉这个合数

如果 是合数，他肯定包含最小质因子，如果在由 筛 的过程中, i % primes[j] == 0，也就是 的最小质因子是 ，这时必须停止筛选，否则会出现重复筛选，也就是用 筛选掉了 ，然而这个数应该由 筛选掉的

代码实现

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; // 合数执行
        }
    }
}

是质数就筛掉 与 数组中所有质数的乘积

是非质数筛掉 与 数组中所有小于最小质因子的乘积

在 的值大于 的时候，线性筛的使用时间大约是埃氏筛的 ，因此大多情况下我们使用线性筛，但埃氏筛的思想值得学习领悟!

埃氏筛是希腊人发明的不是埃及人（Doge）

题解

#include <iostream>

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

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

int main()
{
    a[1] = 1;
    
    for (int i = 2; i <= 5e6; i++)
    {
        if (!st[i]) primes[cnt++] = i;
        
        
        for (int j = 0; primes[j] <= 5e6 / i; j++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
    
    
    for (int i = 0; i < cnt; i++)
    {
        unsigned long long d = primes[i];
        unsigned long long times = d;
        
        a[d] = 1;
        
        if (d * d > 5e6 || d * d <= 0) continue;
        
        while (d && d <= 5e6)
        {
            d *= times;
            if (d > 5e6 || d <= 0) continue;
            a[d] = 1;
        }
    }
    
    for (int i = 1; i <= N - 10; i++)
        a[i] += a[i - 1];
    
    int n; cin >> n;
    
    cout << n - a[n] << endl;
    
    return 0;
}

联系我?

None3548393247@163.com

Good Night, Algorithm!

#include <iostream>

int main()
{
    std::cout << "Welcome to XNL Coding!" << std::endl;
    return 0;
}

>>> XNL
>>> 2024/9/26