20 O 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 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.