Análise Experimental do Crivo de Eratóstenes: Vericação de Complexidade e Comparação com a Variante Segmentada

A identificação de números primos é um problema central na teoria dos números, com aplica-
ções diretas em criptografia e segurança computacional [2]. O Crivo de Eratóstenes, atribuído ao
matemático grego Eratóstenes de Cirene (c. 276–194 a.C.), permanece como um dos métodos mais
utilizados para gerar tabelas de primos até um limite N , com complexidade teórica O(N log log N )
[1]. Embora essa estimativa seja bem estabelecida na literatura, a sua verificação empírica e a
análise comparativa com variantes algorítmicas constituem temas relevantes para a formação em
computação científica, pois permitem ao estudante de graduação confrontar a teoria assintótica
com o comportamento real dos algoritmos.
O presente trabalho, desenvolvido no âmbito de um projeto de Iniciação Científica, investigou
duas frentes: (i) a verificação experimental da complexidade assintótica do crivo clássico, por meio
de medições de tempo de execução para limites crescentes; e (ii) a comparação de desempenho
e consumo de memória entre o crivo clássico e sua variante segmentada. O objetivo foi produzir
evidências experimentais que ilustram tanto a validade da estimativa teórica quanto o compromisso
entre tempo de execução e uso de memória que distingue as duas abordagens.
A fundamentação teórica do crivo apoia-se no seguinte resultado, cuja demonstração pode
ser encontrada em Hefez [4]: se um número natural n > 1 não é divisível por nenhum primo
p com p2 ≤ n, então n é primo. Com efeito, caso n fosse composto, seu menor fator primo
q satisfaria q 2 ≤ n, contradizendo a hipótese. Esse resultado
√ garante que, para obter todos os
primos até N , basta eliminar os múltiplos de cada primo p ≤ ⌊ N ⌋ [5]. O crivo clássico implementa
essa eliminação sobre um vetor booleano de tamanho N , o que implica complexidade de tempo
O(N log log N ) e consumo de memória O(N ).
A variante segmentada, descrita por Sorenson [6] e detalhada por Crandall e Pomerance
[3],
√
particiona o intervalo [2, N ] em blocos de tamanho fixo ∆. Após obter os primos até N pelo
crivo√clássico, cada bloco é peneirado individualmente, de modo que a memória auxiliar se reduz
a O( N + ∆). O parâmetro ∆ é tipicamente escolhido de acordo com o tamanho da cache L1 do
processador, favorecendo a localidade de acesso à memória. A complexidade de tempo permanece
O(N log log N ), porém com constantes que dependem da eficiência do acesso à hierarquia de cache;
observou-se um comportamento aparentemente superlinear para N menor do que a capacidade
da cache L1 (quando os dados do vetor cabem inteiramente na cache e o custo por operação é
mínimo), seguido de estabilização da razão t̄(N )/[N ln(ln N )] à medida que N supera esse limiar
e os cache misses passam a dominar o custo de acesso à memória.

A metodologia experimental seguiu duas etapas. Na primeira, o crivo clássico foi implementado
em Python 3 e executado para limites N ∈ {103 , 104 , 105 , 106 , 107 } — intervalo adotado em razão
das restrições de tempo de execução e consumo de memória inerentes ao ambiente interpretado
do Python 3 —, com múltiplas repetições para cada valor. Para cada N , registrou-se a medi-
ana do tempo de execução t̄(N ) e calculou-se a razão t̄(N )/[N ln(ln N )]. A corretude de ambas
as implementações foi validada comparando-se os valores de π(N ) obtidos com os tabelados em
[3]: π(103 ) = 168, π(104 ) = 1 229, π(105 ) = 9 592, π(106 ) = 78 498 e π(107 ) = 664 579, todos
reproduzidos com exatidão por ambos os crivos.
Na segunda etapa, a variante segmentada foi implementada com segmentos de tamanho fixo
∆ = 32 KB, compatível com caches L1 usuais, e submetida aos mesmos limites. Os indicadores
comparados foram a mediana do tempo de execução e o consumo de memória de cada variante.
Observou-se que, em Python, o crivo clássico apresentou menor tempo de execução em todos os
limites avaliados — de 2,4× mais rápido em N = 103 a 2,6× mais rápido em N = 107 —, em razão
da ausência de custo de gerenciamento de segmentos no laço interpretado. Em contrapartida, a
variante segmentada demonstrou consumo de memória significativamente inferior: opera com um
buffer auxiliar de tamanho fixo ∆ independentemente de N , ao passo que o crivo clássico demanda
um vetor proporcional a N . Para N = 107 , o vetor do crivo clássico ocupou aproximadamente
10 MB, enquanto a variante segmentada utilizou apenas 36 KB de memória auxiliar — uma redução
de 278×.
Essa diferença ilustra o compromisso clássico entre tempo e espaço discutido por Cormen et al.
[1]: o crivo segmentado viabiliza a peneiração para limites nos quais o vetor do crivo clássico não
caberia em memória principal. Além disso, em linguagens compiladas como C ou Fortran, espera-
se que a melhor localidade de cache da variante segmentada reduza ou até inverta a diferença de
tempo observada em Python [6].
Como desdobramentos futuros, pretende-se estender a comparação ao Crivo de Atkin e in-
vestigar o impacto da linguagem de implementação sobre o desempenho relativo dos algoritmos,
confrontando os resultados em Python com implementações em C.
Agradecimentos
O primeiro autor agradece ao Departamento de Matemática da UFRRJ pelo apoio ao projeto
de Iniciação Científica.
Referências
[1]Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Algoritmos:
Teoria e Prática. 3a ed. Rio de Janeiro: Elsevier, 2012.
[2]S. C. Coutinho. Números Inteiros e Criptografia RSA. 2a ed. Rio de Janeiro: IMPA/SBM,
2005.
[3]Richard Crandall e Carl Pomerance. Prime Numbers: A Computational Perspective.
2a ed. New York: Springer, 2005.
[4]Abramo Hefez. Aritmética. Coleção PROFMAT. Rio de Janeiro: SBM, 2006.
[5]Donald E. Knuth. The Art of Computer Programming, Vol. 2: Seminumerical Al-
gorithms. 3a ed. Reading, MA: Addison-Wesley, 1997.
[6]Jonathan Sorenson. “An Analysis of the Segmented Sieve of Eratosthenes”. Em: Congressus
Numerantium 81 (1990), pp. 67–80.