Desempenho do Crivo de Eratóstenes com Bitset e OpenMP
Resumo
Este trabalho avalia o Crivo de Eratóstenes segmentado com representação bitset e OpenMP. Duas versões paralelas (BOOL e BITSET, ambas com 8 threads) foram testadas de 108 a 1012, obtendo speedup entre 0,93× e 1,07×, com a versão BITSET reduzindo o uso de memória em 71%.
Referências
Crandall, R. and Pomerance, C. (2012). Prime Numbers: A Computational Perspective. Mathematics and Statistics. Springer New York.
Dagum, L. and Menon, R. (1998). Openmp: an industry standard api for shared-memory programming. IEEE Computational Science and Engineering, 5(1):46–55.
Oliveira e Silva, T., Herzog, S., and Pardi, S. (2014). Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4 · 1018. Mathematics of Computation, 83(288):2033–2060.
OpenMP (2020). OpenMP Application Program Interface Version 5.1.
Sorenson, J. P. (1998). Trading time for space in prime number sieves. In Proceedings of the 3rd International Algorithmic Number Theory Symposium (ANTS-III), volume 1423 of Lecture Notes in Computer Science, pages 179–195, Berlin, Heidelberg. Springer.
Dagum, L. and Menon, R. (1998). Openmp: an industry standard api for shared-memory programming. IEEE Computational Science and Engineering, 5(1):46–55.
Oliveira e Silva, T., Herzog, S., and Pardi, S. (2014). Empirical verification of the even Goldbach conjecture and computation of prime gaps up to 4 · 1018. Mathematics of Computation, 83(288):2033–2060.
OpenMP (2020). OpenMP Application Program Interface Version 5.1.
Sorenson, J. P. (1998). Trading time for space in prime number sieves. In Proceedings of the 3rd International Algorithmic Number Theory Symposium (ANTS-III), volume 1423 of Lecture Notes in Computer Science, pages 179–195, Berlin, Heidelberg. Springer.
Publicado
02/09/2026
Como Citar
VIEIRA, Hiago Gimenez; LOPES, Maria Fernanda Fuchs; MANSO, Fernando C. G.; FABRÍCIO FILHO, João.
Desempenho do Crivo de Eratóstenes com Bitset e OpenMP. In: ESCOLA REGIONAL DE ALTO DESEMPENHO DE SÃO PAULO (ERAD-SP), 17. , 2026, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 73-76.
DOI: https://doi.org/10.5753/eradsp.2026.30769.
