info prev up next book cdrom email home

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,


\begin{displaymath}
\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,
\end{displaymath} (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

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

Let $m_k\equiv p_1p_2\cdots p_k$, then
$\displaystyle \phi(m_k,k)$ $\textstyle =$ $\displaystyle \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$  
  $\textstyle =$ $\displaystyle m_k-\sum {m_k\over p_i}+\sum {m_k\over p_ip_j} -\ldots$  
  $\textstyle =$ $\displaystyle m_k\left({1-{1\over p-1}}\right)\left({1-{1\over p_2}}\right)\cdots\left({1-{1\over p_k}}\right)$  
  $\textstyle =$ $\displaystyle \prod_{i=1}^k (p_i-1)=\phi(m_k),$ (4)

where $\phi(n)$ is the Totient Function, and
\begin{displaymath}
\phi(sm_k+t,k)=s\phi(m_k)+\phi(t,k),
\end{displaymath} (5)

where $0\leq t\leq m_k$. If $t>m_k/2$, then
\begin{displaymath}
\phi(t,k)=\phi(m_k)-\phi(m_k-t-1,k).
\end{displaymath} (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




© 1996-9 Eric W. Weisstein
1999-05-26