Crivo de primos e espiral de Ulam

Veja o Crivo de Eratóstenes eliminar os compostos, ou observe os primos numa espiral de Ulam.

Exemplo resolvido — Crivo de primos e espiral de Ulam

π(100)	25 primos
N / ln N	21.7(13.1% erro)
Li(N)	29.1(16.3% erro)
Pares gêmeos	8 pares
Lacuna máxima	8

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Crivo de primos e espiral de Ulam

O painel imprime dois tipos distintos de número, e vale a pena separá-los antes de ler mais alguma coisa. π(N) é uma contagem — quantos primos o crivo deixou realmente de pé, 25 em N = 100 e 95 em N = 500, exata e sem arredondamento. As duas linhas por baixo são estimativas dessa mesma contagem. O teorema dos números primos afirma que uma delas acerta o quociente no limite; não afirma que acerta o número. São promessas muito diferentes, e é na coluna do erro que a diferença aparece.

O que significa cada símbolo

N: o teto até ao qual se criva, e a única entrada. O cursor vai até 10000.
π(N): a quantidade de primos que não excedem N. Contada, não estimada — são simplesmente as casas que o crivo não riscou.
N / ln N: a estimativa mais simples dessa contagem. Em todo o N que este cursor alcança fica abaixo da verdade.
Li(N): o logaritmo integral ∫₂ᴺ dt/ln t, uma estimativa mais fina. Em todo o N que este cursor alcança fica acima da verdade.

De onde vem a fórmula

O crivo nunca pergunta se um número é primo. Começa no 2 e risca todos os múltiplos de 2, passa ao número seguinte ainda de pé, risca todos os seus múltiplos e repete. A primalidade não é testada; é o que sobra.
Basta riscar múltiplos de primos até √N. Se um número n ≤ N é composto, então n = a·b com a ≤ b, logo a ≤ √n ≤ √N — todo o composto tem um divisor no máximo igual à raiz, e por isso já foi riscado quando chegou a vez desse divisor. Crivar até 100 exige apenas as passagens do 2, 3, 5 e 7.
Conta os sobreviventes e tens π(N) exatamente. É por isso que a linha de cima é um facto e as duas de baixo são opiniões: o crivo produz a contagem como subproduto de terminar.
Agora compara. O teorema dos números primos diz que π(N) · ln N / N → 1 quando N cresce. Repara no que ele não diz: um quociente que tende para 1 permite que o erro percentual continue grande durante muitíssimo tempo — e a linha seguinte mostra exatamente isso.

Como ler o que vê

Lê os dois valores de erro como uma corrida e muda o N. Em N = 100 a estimativa grosseira vai à frente: 13.1% contra os 16.3% de Li. Vai até N = 200 e inverte-se — 17.9% contra 6.9% — e nunca mais se inverte. Mas o que interessa mesmo observar é aquilo que N/ln N não faz. Ao longo de duas ordens de grandeza o seu erro dá 14.8%, 13.1%, 15.3%, 13.8%, 12.2%: oscila e quase não melhora. Li, no mesmo intervalo, passa de 16.3% para 2.8%. Ambas as estimativas cumprem o teorema dos números primos; só uma serve nas escalas que consegues ver. Os sinais são igualmente constantes — aqui N/ln N fica abaixo da contagem em todo o N, e Li fica acima.

Pressupõe: Que N é suficientemente pequeno para ser crivado por inteiro: a contagem é exata porque cada número até N é mesmo guardado e riscado, e é por isso que o teto é 10000 e não 10¹⁰. As percentagens de erro são tomadas em relação a π(N), pelo que medem as estimativas e nunca a contagem.
Falha quando: Li(N) > π(N) em todo o N que esta página consegue alcançar, o que lhe dá ar de lei. Não é. Littlewood provou em 1914 que a diferença muda de sinal infinitas vezes, portanto existem valores de N em que Li fica aquém — e no século que passou ninguém exibiu um único. Bays e Hudson colocaram o primeiro cruzamento abaixo de cerca de 1.4×10³¹⁶ em 1999, e desde então ninguém o estreitou. Esta página mostra-te, então, um padrão que está provado não ser universal, e nenhuma posição do cursor alcança o contraexemplo. Essa distância entre o que se vê e o que é verdade é a forma honesta deste assunto.

O rarefazer que vê na grelha é a parte que ninguém consegue demonstrar 🖖

A distribuição precisa dos primos é controlada pelos zeros da função zeta de Riemann ζ(s). Todos os 10¹³ zeros não triviais conhecidos estão sobre a linha crítica Re(s) = 1/2. Provar isso para todos os zeros daria os limites mais precisos possíveis para a contagem de primos — e renderia o Prêmio do Milênio de 1 milhão de dólares. Até 2025, permanece sem prova.

Peneirar em vez de testar 🖖

O crivo de Eratóstenes encontra os primos por eliminação, sem testar cada número. Comece no 2, risque todos os seus múltiplos, salte para o próximo número sobrevivente e repita; o que nunca é riscado é primo. O truque engenhoso: para peneirar todos os números até n, basta remover os múltiplos dos primos até √n. Assim, para tudo abaixo de 100 basta riscar os múltiplos de 2, 3, 5 e 7.

O rabisco entediado de Ulam 🖖

Em 1963, o matemático Stanisław Ulam, entediado durante uma palestra, rabiscou os inteiros numa espiral quadrada e sombreou os primos — e surgiram faixas diagonais surpreendentemente nítidas. Essas diagonais seguem fórmulas quadráticas ricas em primos, como o n² + n + 41 de Euler, que produz um primo para cada n de 0 a 39. Por que certas diagonais permanecem tão densas ainda não é totalmente compreendido.

Problemas resolvidos na íntegra

Crivar os 25 primos abaixo de 100 à mão 5 passos
Existem 25 números primos abaixo de 100. Passe-os pelo crivo à mão — dá menos trabalho do que imaginaria — e depois teste o teorema dos números primos numa amostra demasiado pequena para ele.
1. A poupança do crivo é a razão pela qual ele merece um nome. Se n ≤ 100 for composto, fatora-se como ab, e o fator menor não pode exceder √100 = 10. Portanto, eliminar os múltiplos de todos os primos até 10 remove todos os compostos existentes: quatro primos fazem todo o trabalho.
  
  $n \leq 100 composite ⟹ n = ab with min (a, b) \leq 100 = 10$
2. Risque os múltiplos de 2, 3, 5 e 7, cada um começando no seu próprio quadrado, porque tudo o que está abaixo disso já foi eliminado. Sobrevivem vinte e cinco números.
  
  $strike multiples of 2, 3, 5, 7 from 4 upward ⟹ π (100) = 25$
3. O teorema dos números primos diz que a contagem é assintoticamente N/ln N. Para N = 100 isso dá 21,7.
  
  $π (N) \sim \frac{N}{ln N} : \frac{100}{ln 100} = \frac{100}{4.6052} = 21.7$
4. Está 13% abaixo, o que é aceitável para um resultado assintótico em 100. Lido ao contrário, continua a ser útil aqui: a densidade de primos perto de N é 1/ln N, pelo que cerca de 22% dos números perto de 100 são primos, contra 7,2% perto de um milhão. Os primos escasseiam de forma logarítmica, o que é de facto muito lentamente.
  
  $\frac{25 - 21.7}{25} = 13.1%, \frac{1}{ln 100} = 21.7% vs \frac{1}{ln 1 0 ^{6}} = 7.2%$
5. Os intervalos concordam. O intervalo médio abaixo de 100 é 100/25 = 4, e o maior é 8 — a sequência de 89 a 97. O dobro da média, e nada pior.
  
  $mean gap = \frac{100}{25} = 4, largest = 97 - 89 = 8$
Resposta

O crivo dá π(100) = 25 e a ferramenta apresenta a estimativa em 21,7, 13,1% abaixo. Esse erro não é uma falha do teorema; é a taxa de convergência do teorema tornada visível, e a convergência é notoriamente pausada — aumente N para 10 000, quatro ordens de grandeza acima, e a estimativa continua abaixo por dois dígitos. O que se mantém em todas as escalas é a leitura da densidade. Um número em cada 4,6 perto de 100 é primo, um em cada 13,8 perto de um milhão, e como o logaritmo cresce tão devagar, os primos nunca se esgotam e nem sequer se tornam verdadeiramente raros.

$π (100) = 25 from four primes; \frac{N}{ln N} = 21.7 (13.1% low)$
A estimativa óbvia para 8 pares gémeos abaixo de 100 6 passos
O painel conta 25 primos abaixo de 100 e 8 pares de gémeos. O primeiro número tem uma estimativa célebre que chega aos 13 %. Experimente a estimativa óbvia para o segundo — e veja-a falhar por um fator que tem nome.
1. Tome a contagem e a estimativa impressas como ponto de partida: perto de N um número é primo com probabilidade cerca de 1/ln N, e em N = 100 isso dá uns 0,2171.
  
  $π (100) = 25, \frac{N}{ln N} = \frac{100}{4.6052} = 21.7$
2. Suponha agora que n e n+2 são independentes. Se cada um é primo com probabilidade 1/ln N, ambos o são com o quadrado disso.
  
  $P_{1} \approx \frac{1}{ln N} = 0.2171 ⟹ P_{2} \approx P_{1}^{2} = \frac{1}{( ln N ) ^{2}}$
3. Multiplique por N e compare com a ferramenta. A estimativa dá 4,72 pares gémeos abaixo de 100; o crivo encontrou 8. Não fica um pouco aquém: fica 40 % aquém.
  
  $N P_{2} = \frac{100}{21.208} = 4.72 ⟷ π_{2} (100) = 8$
4. A independência é o passo falso, e basta um primo para o mostrar. Tome um primo ímpar p: um n ao acaso é eliminado por p uma vez em cada p, mas o par é eliminado sempre que n ou n+2 for divisível por p, o que são dois restos em p. A taxa de sobrevivência é (p−2)/p, e não o quadrado de (p−1)/p que a independência supunha.
  
  $p > 2 : n \equiv 0 \lor n + 2 \equiv 0 (mod p) ⟹ \frac{p - 2}{p} \neq = (\frac{p - 1}{p})^{2}$
5. Multiplique essa correção sobre todos os primos ímpares e ela converge para uma constante. O seu dobro é 1,3203, e aplicá-la eleva a estimativa a 6,23.
  
  $2 C_{2} = 2 p > 2 \prod \frac{p ( p - 2 )}{( p - 1 ) ^{2}} = 1.3203 ⟹ 1.3203 \times 4.72 = 6.23$
6. Continua abaixo de 8 em N = 100 — a estimativa é assintótica e 100 é um número pequeno. Converge: 156 pares previstos abaixo de 10⁴, 6917 abaixo de 10⁶.
  
  $N = 1 0^{4} : 156 N = 1 0^{6} : 6917$
Resposta

A contagem ingénua é 4,72, a corrigida 6,23, e a verdade é 8 — e o fator de correção 1,3203 é um produto infinito sobre os primos. Essa constante é o preço de supor independência onde não a há, e tem a forma de quase todas as perguntas difíceis da área: os primos são suficientemente aleatórios para que uma heurística funcione, e suficientemente estruturados para que ela precise de uma correção que ninguém sabe deduzir do nada. A conjetura dos primos gémeos afirma que a esta estimativa nunca faltam pares, e continua em aberto.

$π_{2} (N) \sim 2 C_{2} \frac{N}{( ln N ) ^{2}}, 2 C_{2} = 1.3203 : 4.72 \to 6.23 ⟷ 8$

Referências (4)

Why the page’s most convincing pattern is not a law — the difference changes sign infinitely often: J. E. Littlewood, "Sur la distribution des nombres premiers." Comptes Rendus de l’Académie des Sciences, Paris 158, 1869–1872, 1914. No DOI: the volume predates them.
How far the first sign change has been pinned down, and where the 1.4×10³¹⁶ comes from: C. Bays & R. H. Hudson, "A new bound for the smallest x with π(x) > li(x)." Mathematics of Computation 69, 1285–1296, 1999.
How far the Riemann hypothesis has actually been verified — note this is a bound on height, a different measure from a count of zeros: D. J. Platt & T. S. Trudgian, "The Riemann hypothesis is true up to 3·10^12." Bulletin of the London Mathematical Society 53, 792–797, 2021.
The prize, and its official problem statement: Clay Mathematics Institute, Millennium Prize Problems — the Riemann Hypothesis.

Pela equipa 42Math · Atualizado 2026-06-20

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Matemática →

Problemas de exemplo

Pequeno (100) - Aplique o crivo até 100 e a estimativa mais rudimentar vence: N/ln N dá 21,7, um desvio de 13,1%, enquanto Li(100) = 29,1 falha por 16,3%. Esta é a única predefinição em que tal acontece. Avance para 500 e o erro de Li desce para 6,2%. O de N/ln N fixa-se nos 15,3% e aí permanece.
Médio (500) - 95 primos abaixo de 500, em 24 pares gémeos. O maior intervalo é de 14: a extensão entre 113 e 127 sem um único número primo. Este recorde mantém-se intacto até 523, onde se abre um salto de 18. Um intervalo recorde não cresce de forma regular com N. Fica à espera.
Colunas frias - 154 primos abaixo de 900, em 35 pares gémeos. Continue até 1000 e encontrará mais 14 primos, mas nem um único par gémeo novo: o último é formado por 881 e 883. Os gémeos escasseiam mais depressa do que os primos. A questão de saber se alguma vez terminam continua em aberto.
Ulam 400 - Os mesmos 78 primos do modo de grelha, reposicionados numa espiral quadrada. Nada mudou nos números — as faixas diagonais resultam da posição em que a espiral coloca cada inteiro, e é por isso que uma imagem consegue sugerir padrões que a aritmética não confirmou.
TNP (1000) - π(1000) = 168. A expressão N/ln N dá 144,8, falhando por 13,8%; Li(1000) dá 177,0, falhando por 5,3%. Ambas cumprem o Teorema dos Números Primos. Contudo, em qualquer N abrangido por esta ferramenta, apenas uma delas é útil — e a função Li situa-se sempre acima da contagem real.