筛质数

筛质数（线性、埃氏、朴素）

​ 朴素筛法的时间复杂度大概为nlog(n)

​ 埃氏筛法的时间复杂度大概为n(log(log n))

​ 线性筛法的时间复杂度为O(n)

1、朴素筛法

​ 思路

​ primes[] 存储筛选出的质数， st[i] 代表 i 是否为指数，false为质数

​ 对于循环里每一个i,将其的倍数筛掉。

​ 时间复杂度 O(nlogn)：

​ 对于朴素筛法的二重循环，运算次数为(n + n / 2 + n / 3 + .... + n / n) = n* (1 + 1/2 + 1/3 + ... + 1/n)

​ 其中(1 + 1/2 + 1/3 + 1/4 + ... + 1/n)的值：

​

​

​ 综上 时间复杂度为nlogn

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1000010;
int primes[N];
int cnt;
bool st[N];
int 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] = true;
    }
    return cnt;
}
int main()
{
    cin >> n;
    int cnt = get_primes(n);
    cout << cnt << endl;
}

2、埃氏筛法

​ 思路

​ 对朴素筛法进行优化，对于 i ，如果只用i 的质因数去筛掉i,可以进一步优化i被重复筛选的次数。

​ 例如i == 8,对于朴素筛法，2，4,都会把 8 给筛掉，即 8 被重复筛除了2次。而用质因数筛的话，8只会被筛掉1次，故埃氏筛法对朴素筛法来说有进一步的优化。

1 - n 之间质因数的个数 为 `n / ln n` 

​ 埃氏筛法的时间复杂度为 O(nlog(logn))：

​ 时间复杂度分析如朴素筛法：

​ 运算次数为 n(1 + 1/2 + 1/3 + 1/5 + 1/7 +... + 1/n) 即括号内为1/x 的和，其中 x 为小于n的质数

​ 时间复杂度为 O(nlogn(logn))

​ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1000010;
int primes[N];
int cnt;
bool st[N];
int 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] = true;
        }
    }
    return cnt;
}
int main()
{
    cin >> n;
    int cnt = get_primes(n);
    cout << cnt << endl;
}

3、线性筛法

​ 思路

​ 朴素筛法和埃氏筛法在筛质数过程中都存在重复筛除的情况，当每个数只会被其最小的质因数筛除时，每个数只会被筛除一次，即可达到线性的时间复杂度。

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] 作为primes[j] * i的最小质因数，即可保证primes[j] * i 只被筛除1次。如何保证primes[j]是primes[j] * i的最小质因数?

​ 如果 i % primes[j] != 0,则primes[j] 小于 i的最小质因数，则primes[j] * i的最小质因数是 primes[j]

​ 如果 i % primes[j] == 0 则 primes[j] 是 i 的最小质因数，那么primes[j] * i 的最小质因数依然是 primes[j]

​ 综上，每个数只会被自己的最小质因数筛掉，不存在重复筛除，时间复杂度为O(n)

​ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
const int N = 1000010;
int primes[N];
int cnt;
bool st[N];
int 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;
        }
    }
    return cnt;
}
int main()
{
    cin >> n;
    int cnt = get_primes(n);
    cout << cnt << endl;
}