imicola's Blog

素数筛

5分钟阅读

数学 数论 素数

9 素数筛

9.1 一般双重筛

  • 通过不断试除来判断某一数字有无因数
  • 时间复杂度为
bool prime(long long i)
{
    if (i == 2)
        return 1;
    else if (i == 1)
        return 0;
    for (size_t k = 2; k * k <= i; k++) {
        if (i % k == 0) {
            return 0;
        }
    }
    return 1;
}
int main()
{
    long long n;
    cin >> n;
    for (size_t i = 2; i <= n; i++) {
        if (prime(i)) {
            cout << i << endl;
        }
    }
    return 0;
}

9.2 埃拉托斯特尼筛法

  • 核心思路是先标记素数，然后把素数的所有倍数全标记为非素数
  • 时间复杂度是
  • 对于任意一个大于的正整数n,那么它的倍就是合数()。利用这个结论，我们可以避免很多次不必要的检测。
    如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
vector<int> prime;
vector<bool> IsPrime(1e7);
 
void Eratosthenes(long long n)
{
    IsPrime[0] = IsPrime[1] = 0; //前两项不为素数，记作0
    for (size_t i = 2; i <= n; i++) //先全部记作1
    {
        IsPrime[i] = 1;
    }
    //memset(IsPrime,1,sizeof(IsPrime)); //似乎使用memset的时间复杂度也是O(N)
    for (size_t i = 2; i <= n; i++)
    {
        //素数筛选
        //从第三项开始，如果这个数被标记为1，就把它记作素数，放入数组 
        //同时从 i*i 项开始，每次将 i 的倍数标记为非素数
        if (IsPrime[i])
        {
            prime.push_back(i);
            if ((long long)i * i > n) continue; //超过n的不计
            for (size_t j = i*i ; j <= n; j += i)
            {
                IsPrime[j] = 0;
            }
        }
    }
}
 
int main()
{
    long long n;
    cin >> n;
    Eratosthenes(n);
    for (auto &&i : prime) cout << i <<endl;
    return 0;
}
  • 我们可以只筛选到来降低操作次数
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
vector<int> prime;
vector<bool> IsPrime(1e7);
 
void Eratosthenes(long long n)
{
    IsPrime[0] = IsPrime[1] = 0; //前两项不为素数，记作0
    for (size_t i = 2; i <= n; i++) //先全部记作1
    {
        IsPrime[i] = 1;
    }
    //memset(IsPrime,1,sizeof(IsPrime)); //似乎使用memset的时间复杂度也是O(N)
    for (size_t i = 2; i*i <= n; i++)
    {
        //素数筛选
        //从 i*i 项开始，每次将 i 的倍数标记为非素数
        if (IsPrime[i])
        {
            for (size_t j = i*i ; j <= n; j += i)
            {
                IsPrime[j] = 0;
            }
        }
    }
    //计入数组
    for (size_t i = 2; i <= n; i++)
    {
        if (IsPrime[i])
        {
            prime.push_back(i);
        }
    }
}
 
int main()
{
    long long n;
    cin >> n;
    Eratosthenes(n);
    for (auto &&i : prime) cout << i <<endl;
    return 0;
}
  • 我们也可以改写0/1来实现非初始化bool数组
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
vector<int> prime;
vector<bool> IsPrime(1e7);
 
void Eratosthenes(long long n)
{
    IsPrime[0] = IsPrime[1] = 0; //前两项不为素数，记作0
    for (size_t i = 2; i*i <= n; i++)
    {
        //素数筛选
        //从 i*i 项开始，每次将 i 的倍数标记为非素数
        if (!IsPrime[i])
        {
            for (size_t j = i*i ; j <= n; j += i)
            {
                IsPrime[j] = 1;
            }
        }
    }
    //计入数组
    for (size_t i = 2; i <= n; i++)
    {
        if (!IsPrime[i])
        {
            prime.push_back(i);
        }
    }
}
 
int main()
{
    long long n;
    cin >> n;
    Eratosthenes(n);
    for (auto &&i : prime) cout << i <<endl;
    return 0;
}

9.3 欧拉筛法

  • 时间复杂度
  • 埃氏筛法仍有优化空间，它会将一个合数重复多次标记。我们可以用改进的筛法欧拉筛来计算
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
 
vector<int> prime;
vector<bool> not_prime(1e7);
 
void Euler(long long &n)
{
    for (size_t i = 2; i <= n; i++)
    {
        //如果该数标记为 0 即 非(非素数),计入素数数组
        if (!not_prime[i])
        {
            prime.push_back(i);
        }
        // 换言之，i 之前被 prime[j] 筛过了
        // 由于 prime 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
        // prime[j] 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break掉
        for (auto &&j : prime)
        {
            if(i*j > n) break;
            not_prime[i*j] = 1;
            if(i%j == 0) break;
        }
    }
}
 
int main()
{
    long long n;
    cin >> n;
    Euler(n);
    for (auto &&i : prime) cout << i << endl;
    return 0;
}

关系图谱