algorithm - Is it possible to come up with a distributed / multi core implementation of a prime sieve. -

i have been working on prime sieve algorithm, , basic implementation working fine me. struggling way divide , distribute calculation on multiple processors.

i know require storage of actual sieve in shared memory area or text file, how 1 go dividing calculation related steps.

any lead help. thanks!

split numbers sections of equal size, each processor responsible 1 of these sections.

another processor (or 1 of processors) generate numbers of multiple needs crossed-off. , pass number each other processors.

each of processors use remainder of section size divided given number , own section index determine offset own section, , loop through , cross off applicable numbers.

---

alternatively, 1 simpler approach using shared memory.

let first processor start crossing off multiple of 2, second multiples of 3, third multiples of 5, etc.

essentially let each processor grab next number array , run it.

if don't well, may end third crossing off multiples of 4, since first didn't 4 yet when third started, it's not crossed off, shouldn't result in more work - take increasingly longer multiple of prime grabbed processor, while first value crossed off processor handling prime, likelihood of redundancy happening decreases quickly.

using shared memory tends risky - if plan on using 1 bit per index, languages don't allow work on level, , you'll end needing bitwise operations (probably bitwise-and) on few bytes make desired changes (although complexity might hidden in api), , many languages not have operation so-called atomic operation, meaning 1 thread can value, , it, , write back, , can come in , value before first thread wrote it, , it, , write after first thread's write, causing first thread's changes lost. there's no simple, efficient fix - need depend on language.