Memory Efficient Multithreaded Incremental Segmented Sieve Algorithm

2023/10/26 by David Kaeli, Ning, Evan, Kaeli, David
Computer Science · #Algorithms and Data Compression #Distributed #FOS: Computer and information sciences #Parallel #Performance (cs.PF) #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.2310.17746

openalex publication_date 2023/10/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Prime numbers are fundamental in number theory and play a significant role in various areas, from pure mathematics to practical applications, including cryptography. In this contribution, we introduce a multithreaded implementation of the Segmented Sieve algorithm. In our implementation, instead of handling large prime ranges in one iteration, the sieving process is broken down incrementally, which theoretically eliminates the challenges of working with large numbers, and can reduce memory usage, providing overall more efficient multi-core utilization over extended computations.

Related

• A distributed prime sieving algorithm based on Scheduling by Multiple Edge Reversal
• Combined Sieve Algorithm for Prime Gaps
• An algorithmic implementation of the Pi function based on a new sieve
• Three Euler's Sieves and a Fast Prime Generator (Functional Pearl)
• Development of sieve of Eratosthenes and sieve of Sundaram's proof