解析数论：求证π(x) = -1 + π(√x) + Σμ(d)⌊x/d⌋

嘿，这个等式其实是勒让德筛法的核心公式，咱们一步步拆解，你就能搞懂√x在这里的作用，以及整个推导逻辑啦！

核心观察：合数的最小素因子性质 #

首先得明确一个关键结论：任何≤x的合数n，它的最小素因子一定≤√x。为什么？假设n是合数，那n可以写成ab（a,b≥2）。如果a和b都大于√x，那ab > √x*√x = x，这和n≤x矛盾。反过来，所有>√x且≤x的正整数，要么是1，要么是素数——因为如果它是合数，就会有≤√x的素因子，直接矛盾。

这个性质把素数分成了两部分：

• 一部分是≤√x的素数，数量是π(√x)
• 另一部分是>√x且≤x的素数，数量是π(x) - π(√x)

用容斥原理计数“不被小素数整除的数” #

我们用莫比乌斯函数的容斥性质来计算：≤x且不被任何≤√x的素数整除的正整数个数。

设S是所有≤√x的素数集合，那么符合条件的数的个数可以用莫比乌斯函数求和表示：
Σ_{d:素因子均≤√x} μ(d)⌊x/d⌋

这里的d遍历所有素因子属于S的正整数——不过注意，当d有平方因子时，μ(d)=0，所以这些项不会贡献，实际有效项是S中素数生成的无平方因子数（包括d=1）。

关联到素数个数 #

刚才说了，“不被任何≤√x的素数整除的数”包含两类：

1. 数字1
2. 所有>√x且≤x的素数（它们的素因子都>√x，自然不被S中的素数整除）

所以这个计数结果等于：1 + (π(x) - π(√x))

把这个和容斥的等式结合起来：
1 + π(x) - π(√x) = Σ_{d:素因子均≤√x} μ(d)⌊x/d⌋

整理得到目标等式 #

把式子移项整理：
π(x) = -1 + π(√x) + Σ_{d:素因子均≤√x} μ(d)⌊x/d⌋

这就是你要证明的等式啦！

举个小例子验证 #

比如取x=10，√x≈3.16，≤√x的素数是2、3：

• π(√x)=π(3)=2
• 求和项d遍历1、2、3、6：
  • μ(1)⌊10/1⌋=110=10
  • μ(2)⌊10/2⌋=-15=-5
  • μ(3)⌊10/3⌋=-13=-3
  • μ(6)⌊10/6⌋=11=1
    求和结果：10-5-3+1=3
• 代入右边：-1 + 2 + 3 = 4，而π(10)=4（素数2、3、5、7），完全吻合！

内容的提问来源于stack exchange，提问作者Faust