Un set migliore di numero primo simultaneo in uscita

Question

Dopo aver esaminato il codice del setaccio del numero primo e visto come funziona la struttura concorrente , l'ho trovato estremamente elegante. Tuttavia, è anche estremamente inefficiente e IIRC, equivalente all'operazione O (n^2) di test della divisibilità del numero m per dividendolo per ogni numero inferiore a m. Immagino che potrei invece modificare per utilizzare l'operazione O (n^1.5) di controllo della divisibilità di m dividendolo per ogni numero minore o uguale a sqrt (m). Tuttavia, questo si è rivelato molto più difficile di quanto mi aspettassi.

So che questo è più di una questione algoritmi, ma è anche uno estremamente rilevanti per la concorrenza. Come implementare la versione O (n^1.5) dell'algoritmo?

Answer 1

Un posto da cercare è stackoverflow, ad esempio, la domanda Concurrent Prime Generator. Tra le risposte c'è quella che usa Go and channels.

Answer 2

Le implementazioni di setaccio primario eleganti ma inefficienti sono già ben note alla comunità di programmazione funzionale. Questo paper di Melissa O'Neill offre una buona panoramica dei pigmenti "stream" pigri, oltre a presentare alternative efficienti. (Utilizza Haskell, ma dovrebbe comunque essere una buona lettura)

Answer 3

Il setaccio di Eratostene identifica il primo p_i all'iterazione i e elimina tutti i multipli di p_i dalla considerazione in iterazioni successive. Detto questo, l'unica cosa che puoi parallelizzare qui è l'operazione di potatura. Questo può essere accelerato solo di un fattore costante, quindi non cambierai il big-O dell'algoritmo in questo modo.