[Done]Sieve of Eratosthenes 素数区间筛[Both Done 20260505]

Primes are the “atoms” of mathematics—they can’t be broken down, yet they build everything else. When it comes to competitive programming, handling primes usually falls into two categories: Primality Testing (checking if one specific number is prime) and Sieve Algorithms (finding all primes in a range).

Here is a comprehensive guide to these algorithms.

---

1. Single Number Primality Testing

A. Trial Division (The “Old Reliable”)

This is the most straightforward method. If a number $n$ is composite, it must have a factor less than or equal to $\sqrt{n}$. By checking all integers from $2$ up to $\sqrt{n}$, we can determine primality.

• Complexity: $O(\sqrt{n})$
• Best for: $n \le 10^{12}$ (in local environments) or $10^9$ (within tight time limits).
• Logic:

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

B. Miller-Rabin Primality Test (The “Big Gun”)

For numbers beyond $10^{14}$, trial division is too slow. Miller-Rabin uses Fermat’s Little Theorem ($a^{p-1} \equiv 1 \pmod p$) and the property of quadratic residues to test primality with high probability.

• Complexity: $O(k \log^3 n)$, where $k$ is the number of bases tested.
• Best for: $n \le 10^{18}$ or even larger.
• Note: While technically probabilistic, using specific bases (like 2, 3, 5, 7, 11, etc.) makes it deterministic for all $n < 2^{64}$.

---

2. Range Sieve Algorithms

When you need to know all primes up to $N$, checking each number individually is inefficient. Instead, we use a “Sieve.”

A. Sieve of Eratosthenes (The “Classic”)

The most famous sieve. You start at 2 and “cross out” all of its multiples. Then move to the next uncrossed number (which must be prime) and repeat.

• Complexity: $O(n \log \log n)$
• Best for: $n \le 10^6$.
• Key Insight: The time complexity is derived from the Prime Harmonic Series: $\sum \frac{1}{p} \approx \log \log n$.
• Logic:

vector<bool> is_prime(N, true);
is_prime[0] = is_prime[1] = false;
for (int p = 2; p * p < N; p++) {
    if (is_prime[p]) {
        for (int i = p * p; i < N; i += p)
            is_prime[i] = false;
    }
}

B. Euler’s Sieve (The “Linear Sieve”)

In Eratosthenes’ sieve, a number like 30 is crossed out multiple times (by 2, 3, and 5). Euler’s sieve optimizes this by ensuring every composite number is crossed out exactly once by its smallest prime factor.

• Complexity: $O(n)$
• Best for: $n \le 10^7$.
• Advantage: Beyond speed, it allows you to precompute other “multiplicative functions” like the Euler Totient ($\phi$) or Möbius function ($\mu$) simultaneously.
• Logic:

vector<int> primes;
bool is_composite[N];
for (int i = 2; i < N; ++i) {
    if (!is_composite[i]) primes.push_back(i);
    for (int p : primes) {
        if (i * p >= N) break;
        is_composite[i * p] = true;
        if (i % p == 0) break; // This ensures 'p' is the SMALLEST prime factor
    }
}

C. Segmented Sieve (The “Long Distance Runner”)

If you need to find primes in a range $[L, R]$ where $R$ is very large (e.g., $10^{12}$) but the range width $(R-L)$ is small (e.g., $10^6$), you cannot use a standard sieve because of memory limits.

The Segmented Sieve uses a “small sieve” up to $\sqrt{R}$ to screen the “large range” using an offset.

• Complexity: $O((R-L) \log \log \sqrt{R} + \sqrt{R})$
• Best for: DMOJ-style problems where the range is far from zero.

---

Summary Comparison

Algorithm	Type	Complexity	Ideal Range (n)
Trial Division	Single Test	$O(\sqrt{n})$	up to $10^9$
Miller-Rabin	Single Test	$O(k \log^3 n)$	up to $10^{18}+$
Naive Sieve	Range Sieve	$O(n\sqrt{n})$	up to $10^4$ (don’t use)
Eratosthenes	Range Sieve	$O(n \log \log n)$	up to $10^6$
Euler Sieve	Range Sieve	$O(n)$	up to $10^7$
Segmented Sieve	Range Sieve	$O(\text{Width} \cdot \log \log \sqrt{R})$	$R \le 10^{12}$, Width $\le 10^7$

Pro-tip: For most contests, the Sieve of Eratosthenes is perfectly sufficient. Use Euler’s Sieve only if you have a very tight time limit or need to perform complex number theory calculations on every number in the range!

数学原理：任何一个合数 $X$，如果它有因数，那么它一定有一个小于等于 $\sqrt{X}$ 的质因数。

• 如果你要检查区间 $[m, n]$ 里的数，这个区间里最大的合数不会超过 $n$。
• 这意味着，这个区间里所有的合数，都能被 $2, 3, 5 \dots \sqrt{n}$ 这些“小质数”给整除。

它们干什么用？

它们就是你的**“标记工具”。你不需要去“判断”一个数是不是质数，你只需要用这些小质数去“排除”**合数。

3. 它们在“筛查”什么？

想象你面前有一排透明的瓶子，代表区间 $[m, n]$ 里的每一个数：

1. 你拿出小质数 2：把所有 2 的倍数的瓶子都贴上“合数”标签。
2. 你拿出小质数 3：把所有 3 的倍数的瓶子都贴上“合数”标签。
3. 你拿出小质数 5……以此类推，直到用完所有 $\sqrt{n}$ 以内的质数。

最后，那些身上干干净净、没被贴标签的瓶子，就是质数！ 这种“排除法”比“一个个问它是谁”要快得多，因为你是在成批成批地处理数字。

埃氏（Eratosthenes），全名埃拉托斯特尼（公元前 276 年 – 公元前 194 年），是一位古希腊的超级天才（博学家）。

关于他有几个很有趣的标签：

• 亚历山大图书馆馆长：当时世界上知识最渊博的人之一。
• 地理学之父：他是第一个计算出地球周长的人，而且误差惊人地小（他只用了两根木棍、影子的角度和一点点几何知识）。
• 绰号 “Beta” (β)：因为他在当时的每一个领域（天文、地理、数学、文学）都是世界第二强。虽然这听起来像是在损他，但其实是夸他全能——在所有领域都能排进前二。

“筛”这个词的由来： 在古代，数学家真的会在木板或纸草纸上写满数字，然后每发现一个合数，就用针在上面戳一个洞。当所有的合数都被戳破后，剩下的板子上全是洞，看起来就像一个滤渣的筛子。