\[
\pi(n)=|\{k\in\{2,\ldots,n\}\mid k\mbox{ é primo}\}|.
\]
Ou seja, $\pi(n)$ é o número dos primos entre $2$ e $n$. É fácil computar o valor de $\pi(n)$ para $n$ pequeno:
\[
\pi(1)=0,\quad \pi(2)=1,\quad \pi(3)=\pi(4)=2,\quad \pi(5)=\pi(6)=3,\ldots
\]
No entanto, se $n$ for grande, determinar o valor de $\pi(n)$ pode ser difícil.
O Crivo de Eratóstenes, é um algoritmo que pode ser usado para obter os primos que são menores ou iguais a um número fixo $n$. A ideia do crivo é a seguinte. Assuma que você quer determinar todos os primos entre $1$ e algum outro número $n$.
- Escreva os números de $1$ até $n$ em uma lista na ordem crescente.
- Comece por eliminar o número $1$ da sua lista, pois ele não é primo.
- O menor número não eliminado na lista é $2$ que é primo. Elimine os múltiplos de $2$ a partir de $4$ da lista, pois eles não são primos.
- Menor número não eliminado depois de $2$ é o $3$. Elimine os múltiplos de $3$ a partir de $3^2=9$ da lista, pois eles não são primos.
- O menor número não eliminado depois de $3$ é o $5$. Ele é primo. Elimine os múltiplos de $5$ da lista a partir de $5^2=25$, pois eles não são primos.
- No passo geral, ache o menor número $p$ depois do último primo encontrado. Este número $p$ será primo. Elimine os múltiplos de $p$ a partir de $p^2$ da lista, pois eles não são primos. Note que os demais múltiplos compostos de $p$ (que são menores de $p^2$) já foram eliminados.
- Repita o passo geral até $p > \sqrt n$.
- Os números que não foram eliminados da lista são os primos entre $1$ e $n$.
Uma implementação simples em Python deste algoritmo é o seguinte.
def eratosthenes( n ):
prims = [ True for i in range(n+1) ]
prims[0] = False; prims[1] = False
sqrn = int(n**(1/2))
for i in range(2,sqrn+1):
if prims[i]:
st = i**2
while st <= n:
prims[st] = False
st = st + i
return prims
O Crivo de Eratóstenes não é um algoritmo eficiente, pois o passo geral precisa ser executada $\sqrt n$ vezes. Na prática (por exemplo, na criptografia), nós precisamos lidar com números com $500$ ou mais algarismos. Se por exemplo, $n\approx 10^{500}$, então $\sqrt n\approx 10^{250}$ e na prática fica impossível realizar a computação até com um supercomputador.
Está bem conhecido que a função $\pi(n)$ pode ser aproximada pelas funções
\[
\lambda(n)=\frac n{\log n}
\]
e
\[
\sigma(n)=\int_2^n \frac{dt}{\log t}.
\]
Por exemplo, o número dos primos entre $1$ e $10.000.000$ é $664579$. Ou seja
\[
\pi(10.000.000)=664579,
\]
enquanto
\[
\lambda(10.000.000)\approx 620420\quad\mbox{e}\quad \sigma(10.000.000)\approx 664917.
\]
Geralmente, a aproximação dada por $\sigma(n)$ é melhor, mas é mais difícil de calcular.
Atualmente (novembro de 2021), o maior primo conhecido é $2^{82.589.933} − 1$. Este número tem $24.862.048$ algarismos na base decimal e foi encontrado em 2018. Este número é um exemplo dos primos de Mersenne, ou seja primos na forma $2^p-1$ onde $p$ é um primo.