This paper is available on arxiv under CC 4.0 license.
Authors:
(1) Evan Ning, Milton Academy & [email protected];
(2) David R. Kaeli, Department of Electrical and Computer Engineering & Northeastern University [email protected].
Table of Links
- Introduction
- Sieve Optimizations
- Mathematical Optimization
- Implementation
- Results and Discussions
- Conclusions, Source Code & References
4.0 Implementation
In Figure 3, we provide a diagram of our multithreaded Sieve algorithm's execution flow when utilizing multiple threads. We show the thread structure and flow of the information. In Figure 4 we provide pseudocode for our implementation. In each iteration, the newly found prime numbers are stored in the Prime Number Data Store, which we currently store in a linked list. The primes are also stored in the Sieve Data Store, but only up to the square root of the numbe,r since we only need to sieve up to the square root of the number. This is because for any prime greater than the square root, P2 would be greater than N and there would be nothing to sieve.