关于素数分布的一个重要结论是素数定理: `pi(x) ~ "li"(x) ~ x/(ln x)`, `quad x to oo`. 其中 `pi(x)` 是 `x` 以内 (即 `le x`) 的素数个数, 而 `"li"(x) = int_0^x dt/(ln t)` `= lim_(epsi to 0^+) int_0^(1-epsi) + int_(1+epsi)^x`. 它的证明比较复杂, 我们只证较弱的结论 `pi(x) = Theta(x/(ln x))`. 换言之, `x` 充分大时, 存在正的常数 `c_1, c_2` 使 `c_1 x/(ln x) le pi(x) le c_2 x/(ln x)`. 此即著名的 Чебышев 不等式.

由素数定理推出 `p_n ~ n ln n`, `p_n` 是第 `n` 个素数.

[来自 zz] 由 `pi(x) ~ x/(ln x)` 取对数得 `ln pi(x) = ln x - ln ln x + o(1)`. 于是 `p_n/(n ln n)` `= p_n/(pi(p_n) ln pi(p_n)` `= (ln p_n)/(ln p_n - ln ln p_n + o(1))` `to 1`.

筛法

用 Eratosthenes 筛法求 100 以内的素数个数.

`sqrt 100 = 10`, 而 10 以内的素数为 2, 3, 5, 7. 对于 `10 lt n le 100`, 只要 `n` 与 2, 3, 5, 7 互素, 就能保证为素数. 而对于 `n le 10`, 只有 1 与 2, 3, 5, 7 互素. 换言之, 100 以内与 2, 3, 5, 7, 互素的整数个数为 `pi(100) - pi(10) + 1`. 记 `P = 2 * 3 * 5 * 7`, 称为一个筛子. `A = {1, cdots, 100}` 是待筛的整数. 定义筛函数为 `S(A, P) = sum_(a in A, (a,P) = 1) 1`, 表示通过了筛选的整数个数. 于是 `S(A, P) = pi(100) - pi(10) + 1`. 又记 `A_d` 为 `A` 中所有 `d` 的倍数, 则 `|A_d| = |__100/d__|`. 由容斥原理, `S(A, P)` `= |A| - |A_2| - |A_3| - |A_5| - |A_7|` `+ |A_(2*3)| + |A_(2*5)| + |A_(2*7)| + |A_(3*5)| + |A_(3*7)| + |A_(5*7)|` `- |A_(2*3*5)| - |A_(2*3*7)| - |A_(2*5*7)| - |A_(3*5*7)|` `+ |A_(2*3*5*7)|` `= 100 - 50 - 33 - 20 - 14 + 16 + 10 + 7 + 6 + 4 + 2` `- 3 - 2 - 1 - 0 + 0` `= 22`. 因此 `pi(100) = S(A, P) + pi(10) - 1 = 22 + 4 - 1 = 25`.

设 `A` 为有限个整数的集合, `A_d` 为 `A` 中所有 `d` 的倍数. 筛子 `P` 为一个正整数, 且 `P` 的所有素因子为 `p_1, cdots, p_s`. 那么 `S(A, P) := sum_(a in A, (a,P) = 1) 1` `= sum_(r=0)^s (-1)^r sum_(i_1 lt cdots lt i_r) |A_(p_(i_1) cdots p_(i_r))|`. 使用 Möbius 函数 `mu(n) = { 1, if n = 1; (-1)^r, if n = p_1 cdots p_r 为不同素数的乘积; 0, if n 含有平方因子 :}` 结论简记为 `S(A, P) = sum_(d | P) mu(d) |A_d|`. 特别当 `A = {1, cdots, n}`, `P = n` 时, 得到 Euler 函数的表达式 `varphi(n) = sum_(d | n) mu(d) n//d` `= n prod_(p | n) sum_(p^a | n) mu(p^a)//p^a` `= n prod_(p | n) (1 - 1//p)`.

利用公式 `sum_(d | P) mu(d) = { 1, if P = 1; 0, if P gt 1 :}` 有 `sum_(a in A, (a,P) = 1) 1` `= sum_(a in A) sum_(d | (a,P)) mu(d)` `= sum_(d | P) mu(d) sum_(a in A, d | a) 1` `= sum_(d | P) mu(d) |A_d|`.

Чебышев 不等式

Чебышев 不等式 记 `pi(x)` 是不超过 `x` 的素数个数, `p_n` 为第 `n` 个素数. 我们有 `color(#663)(1/3 ln 2)x/(ln x)` `lt pi(x)` `lt color(#663)(6 ln 2)x/(ln x)`, `quad AA x ge 2`
`color(#663)(1/(6 ln 2)) n ln n` `lt p_n` `lt color(#663)(8/(ln 2)) n ln n`, `quad AA n ge 2`.

    为证明 `pi(x)` 的上下界, 我们从 `M = (2 m; m)` 的估计入手, `m` 为正整数.
  1. 联系第一章 Kummer 定理的相关内容, 记 `v_p(n)` 为素数 `p` 在 `n` 中的次数, 有 `v_p(n!) = sum_(i ge 1) |__n/p^i__|`. 取对数有 `ln M` `= ln((2m)!) - 2 ln(m!)` `= sum_(p lt 2m) v_p((2m)!) ln p` `- 2 sum_(p le m) v_p(m!) ln p` `= sum_(p le m) [v_p((2m)!) - 2 v_p(m!)] ln p` `+ sum_(m lt p lt 2m) v_p((2m)!) ln p` `= A + B`.
  2. 对 `y gt 0` 有 `0 le |__2y__| - 2|__y__| le 1`, 于是 `0 le (|__(2m)/p^i__| - 2|__m/p^i__|) le 1`, `quad i ge 1`. 上式求和得到 `A` 的系数的估计 `0 le v_p((2m)!) - 2 v_p(m!)` `le sum_(p^i | 2m) 1` `= |__ln(2m)/ln p__|`. 另一方面, `m lt p lt 2m` 时, 显然 `p` 在 `(2m)!` 中的次数为 `1`, 即 `B` 的系数 `v_p((2m)!) = 1`. 于是 `sum_(m lt p lt 2m) ln p` `le ln M` `le sum_(p lt 2m) |__ln(2m)/ln p__| ln p`. 因而 `(pi(2m)-pi(m)) ln m` `le ln M` `le pi(2m) ln(2m)`.
  3. 通过直接估计 `M` 的上下界得到 `M = (2m)/m * (2m-1)/(m-1) cdots (m+1)/1 ge 2^m`;
    `M = (2m; m) lt (1+1)^(2m) = 2^(2m)`.     于是 `pi(2m) ln(2m) ge m ln 2`,
    `(pi(2m)-pi(m))ln m lt 2m ln 2`.
  4. 当 `x ge 6` 时, 取 `m = |__x//2__| gt 2`, 此时成立 `2m lt x lt 3m`, 因此 `pi(x) ln x ge pi(2m) ln(2m)` `ge m ln 2` `gt x/3 ln 2`. 直接验算知上式对 `2 le x lt 6` 也成立; 这证明了不等式的左半部分.
  5. 当 `m = 2^k` 时, `(pi(2^(k+1)) - pi(2^k)) k lt 2^(k+1)`, 又显然 `pi(2^(k+1)) le 2^k`, 两式相加得 `(k+1)pi(2^(k+1)) - k pi(2^k) lt 3 * 2^k`. 令 `k` 从 0 到 `h-1` 求和有 `h pi(2^h) lt 3 * 2^h`. 设 `2^(h-1) lt x le 2^h`, 则 `pi(x) le pi(2^h)` `lt 3 * 2^h//h` `lt 3 * (2 x)/(ln x//ln 2)` `= 6 ln 2 x/(ln x)`. 这证明了不等式的右半部分.
  1. 从 `pi(x)` 的估计出发, 取 `p_n = x`, 得到 `n lt 6 ln 2 p_n/(ln p_n)`. 再由 `p_n gt n` 得 `p_n gt (n ln n)/(6 ln 2)`; 这证明了左半不等式.
  2. `n = 2` 时直接验证右半不等式成立. 下设 `n ge 3`, 因此 `p_n` 为奇素数. 在不等式 `pi(2m) ln(2m) ge m ln 2` 中取 `2m = p_n + 1`, 得 `n ln(p_n+1) ge (p_n+1)/2 * ln 2`, `ln(p_n+1) le ln(2n//ln 2) + ln ln(p_n+1)`. 利用不等式 `ln(1+s) le s`, 取 `s = y//2 - 1` 有 `ln y le y//2 - 1 + ln 2 lt y//2`, `quad y gt 0`. 再令 `y = ln(p_n+1)`, 有 `ln ln(p_n+1) lt 1/2 ln(p_n+1)`. 由 得 `ln(p_n+1) le 2 ln(2n//ln 2) lt 4 ln n`, `quad n ge 3`. 再由 即完成右半不等式的证明.
    Чебышев 函数 两个 Чебышев 函数定义为
  1. `vartheta(x) = sum_(p le x) ln p`, 其中 `p` 为素数;
  2. `psi(x) = sum_(p^a le x) ln p`, 其中 `p` 为素数, `a` 为正整数.
    3. 若定义 Mangoldt 函数为 `Lambda(n) = { ln p, if n = p^a; 0, "otherwise" :}`, 则 `psi(x) = sum_(n le x) Lambda(n)`.

Mangoldt 函数的和函数是对数函数: `sum_(d | n) Lambda(d) = ln n`.

设 `p` 在 `n` 中的次数为 `a_p`, 利用算术基本定理, 左边等于 `sum_(p^a | n) ln p` `= a_p sum_(p | n) ln p` `= ln(prod_(p | n) p^(a_p))` `= ln n`.

`x ge 1` 时, `sum_(n le x) psi(x // n) = ln(|__x__|!)`.

由定义, 左边等于 `sum_(n le x) sum_(k le x//n) Lambda(k)` `= sum_(n le x) sum_(n k le x) Lambda(k)` `==^(n k = m) sum_(m le x) sum_(n | m) Lambda(m/n)` `= sum_(m le x) ln m` 等于右边.

    Чебышев 函数是 `pi(x)` 的良好替代, 事实上存在常数 `c_gamma gt 0` 使得
  1. `(ln x - c_gamma) pi(x) lt vartheta(x) lt ln x pi(x)`;
  2. `vartheta(x) le psi(x) le vartheta(x) + sqrt x ln x`.
    以下三个命题等价:
  1. 存在常数 `d_1, d_2 gt 0` 使得 `d_1 x // ln x lt pi(x) lt d_2 x // ln x`;
  2. 存在常数 `d_3, d_4 gt 0` 使得 `d_3 x lt vartheta(x) lt d_4 x`;
  3. 存在常数 `d_5, d_6 gt 0` 使得 `d_5 x lt psi(x) lt d_6 x`;
    4. 以下三个命题等价: `x to oo` 时
  4. `pi(x) ~ x // ln x`;
  5. `vartheta(x) ~ x`;
  6. `psi(x) ~ x`.