勒讓德公式

勒讓德公式計算了小於或等於數字 且不能被前 個素數整除的正整數的數量，

(1)

其中 是向下取整函式。取 ，其中 是素數計數函式，得到

(2)

勒讓德公式成立是因為一個範圍內素數的數量加一等於整數的數量減去該區間內合數的數量。

勒讓德公式滿足遞推關係

(3)

令 ，則

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

其中 是尤拉 Totient 函式，且

(9)

其中 。如果 ，則

(10)

請注意， 不適用於計算大引數的 。更有效的改進是梅塞爾公式。