Número dos primos

Para $n\in\N$, defina
\[
\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 Julia deste algoritmo é o seguinte.

function eratosthenes( n )
	prims = [ true for i in 1:n ]
	prims[1] = false
	
	sqrn = convert( Int64, floor(n^(1/2)))
	
	for i in 2:sqrn
		if prims[i] == true
			st = i^2
			while st <= n
				prims[st] = false
				st += i
			end
		end
	end
	
	return prims	
end

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$ pode ser calculado com a função acima:

julia> pr = eratosthenes( 10^7 );

julia> counter( pr )
Accumulator{Bool, Int64} with 2 entries:
  0 => 9335421
  1 => 664579
  

Obtemos que
\[
\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.