勒让德公式

勒让德公式计算了小于或等于数字 且不能被前 个素数整除的正整数的数量，

(1)

其中 是向下取整函数。取 ，其中 是素数计数函数，得到

(2)

勒让德公式成立是因为一个范围内素数的数量加一等于整数的数量减去该区间内合数的数量。

勒让德公式满足递推关系

(3)

令 ，则

			(4)
			(5)
			(6)
			(7)
			(8)

其中 是欧拉 Totient 函数，且

(9)

其中 。如果 ，则

(10)

请注意， 不适用于计算大参数的 。更有效的改进是梅塞尔公式。