Legendre's Formula

Counts the number of Positive Integers less than or equal to a number $x$ which are not divisible by any of the first $a$ Primes,

$$\phi(x,a)&=\left\lfloor{x}\right\rfloor -\sum\left\lfloor{x... ...loor -\sum\left\lfloor{x\over p_ip_jp_k}\right\rfloor +\ldots,$$ (1)

where $\left\lfloor{x}\right\rfloor$ is the Floor Function. Taking $a=x$ gives

$\phi(x,x)=\pi(x)-\pi(\sqrt{x}\,)+1=\left\lfloor{x}\right\rfloor -\sum_{p_i\leq\sqrt{x}} \left\lfloor{x\over p_i}\right\rfloor$
$+\sum_{p_i<p_j\leq\sqrt{x}}\left\lfloor{x\over p_ip_j}\right\rfloor -\sum_{p_i<p_j<p_k\leq\sqrt{x}}\left\lfloor{x\over p_ip_jp_k}\right\rfloor +\ldots,$
	(2)

where $\pi(n)$ is the Prime Counting Function. Legendre's formula holds since one more than the number of Primes in a range equals the number of Integers minus the number of composites in the interval.

Legendre's formula satisfies the Recurrence Relation

$$\phi(x,a)=\phi(x,a-1)-\phi\left({{x\over p_a}, a-1}\right).$$ (3)

Let $m_k\equiv p_1p_2\cdots p_k$, then

$$\phi(m_k,k) = \left\lfloor{m_k}\right\rfloor -\sum\left\lfloor{m_k\over p_i}\right\rfloor +\sum\left\lfloor{m_k\over p_ip_j}\right\rfloor -\ldots$$

$$= m_k-\sum {m_k\over p_i}+\sum {m_k\over p_ip_j} -\ldots$$

$$= m_k\left({1-{1\over p-1}}\right)\left({1-{1\over p_2}}\right)\cdots\left({1-{1\over p_k}}\right)$$

$$= \prod_{i=1}^k (p_i-1)=\phi(m_k),$$ (4)

where $\phi(n)$ is the Totient Function, and

$$\phi(sm_k+t,k)=s\phi(m_k)+\phi(t,k),$$ (5)

where $0\leq t\leq m_k$. If $t>m_k/2$, then

$$\phi(t,k)=\phi(m_k)-\phi(m_k-t-1,k).$$ (6)

Note that $\phi(n,n)$ is not practical for computing $\pi(n)$ for large arguments. A more efficient modification is Meissel's Formula.

See also Lehmer's Formula, Mapes' Method, Meissel's Formula, Prime Counting Function