查看“︁06-数学相关/01-质数判断与筛法”︁的源代码


== 判断单个质数 ==

<math>O(\sqrt{x})</math>

<syntaxhighlight lang="cpp">
bool is_prime(long long x)
{
    if (x < 2)
        return false;
    for (long long i = 2; i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}
</syntaxhighlight>

== 埃氏筛 ==

<math>O(n\log \log n)</math>

<syntaxhighlight lang="cpp">
const int MAXN = 10'000'000;
bool p[MAXN + 1];

// 筛出 1~n 中的每个数是否为质数
void get_primes(int n)
{
    p[0] = p[1] = false;
    for (int i = 2; i <= n; i++)
        p[i] = true;
    for (int i = 2; i <= n; i++)
        if (p[i])
            for (int j = i + i; j <= n; j += i)
                p[j] = false;
}
</syntaxhighlight>

== 线性筛（欧拉筛） ==

<math>O(n)</math>。每个合数只被其最小质因子筛去。

<syntaxhighlight lang="cpp">
const int MAXN = 10'000'000;
bool p[MAXN + 1];
vector<int> pri;

void get_primes(int n)
{
    for (int i = 1; i <= n; i++)
        p[i] = true;
    p[0] = p[1] = false;
    for (int i = 2; i <= n; i++)
    {
        if (p[i])
            pri.push_back(i);
        for (int j = 0; j < pri.size(); j++)
        {
            if (1LL * i * pri[j] > n)
                break;
            p[i * pri[j]] = false;
            if (i % pri[j] == 0)
                break;
        }
    }
}
</syntaxhighlight>

核心原理：对于每个数 <math>i</math>，用已求出的质数 <math>pri[j]</math> 筛去 <math>i \times pri[j]</math>。当 <math>i</math> 是 <math>pri[j]</math> 的倍数时停止，保证每个合数只被最小质因子筛去。

== 质因数分解 ==

<syntaxhighlight lang="cpp">
// 对 x 进行质因数分解，结果存储在 pairs<质因子, 次数> 中
vector<pair<long long, int>> factor(long long x)
{
    vector<pair<long long, int>> res;
    for (long long i = 2; i * i <= x; i++)
        if (x % i == 0)
        {
            int cnt = 0;
            while (x % i == 0)
                x /= i, cnt++;
            res.push_back({i, cnt});
        }
    if (x > 1)
        res.push_back({x, 1});
    return res;
}
</syntaxhighlight>


[[Category:数学相关]]
[[Category:三三文档]]