Un mejor tamiz de número primo concurrente en go

Question

Después de ver el código del tamiz de número primo y ver cómo funciona la estructura concurrente , me pareció extremadamente elegante. Sin embargo, también es extremadamente ineficiente e IIRC, equivalente a la operación O (n^2) de probar la divisibilidad del número m por dividiéndolo por cada número menor que m. Me imagino que podría en su lugar modificarlo para usar la operación O (n^1.5) de verificar la divisibilidad de m dividiéndola por cada número menor o igual que sqrt (m). Sin embargo, esto resultó ser mucho más difícil de lo que esperaba.

Sé que esto es más una cuestión algorítmica, pero también es uno extremadamente relevante para la concurrencia. ¿Cómo se implementaría la versión O (n^1.5) del algoritmo?

Answer 1

Un lugar para buscar es stackoverflow, por ejemplo, la pregunta Concurrent Prime Generator. Entre las respuestas está una que usa Go and channels.

Answer 2

Las implementaciones de tamices primarios elegantes pero ineficientes ya son bien conocidas por la comunidad de Programación Funcional. Esta paper de Melissa O'Neill ofrece una buena visión general de tamices primarios de "corriente continua" y presenta alternativas eficientes. (Utiliza Haskell, pero debe ser una buena lectura de todos modos)

Answer 3

El tamiz de Eratosthenes identifica primo p_i en la iteración i y elimina todos los múltiplos de p_i de la consideración en sucesivas iteraciones. Dado que, lo único que se puede paralelizar aquí es la operación de poda. Esto solo puede ser acelerado por un factor constante, por lo que no cambiará la gran O del algoritmo de esta manera.