{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T23:54:09Z","timestamp":1768521249220,"version":"3.49.0"},"reference-count":70,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2024,4,14]],"date-time":"2024-04-14T00:00:00Z","timestamp":1713052800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The systematic generation of prime numbers has been almost ignored since the 1990s, when most of the IT research resources related to prime numbers migrated to studies on the use of very large primes for cryptography, and little effort was made to further the knowledge regarding techniques like sieving. At present, sieving techniques are mostly used for didactic purposes, and no real advances seem to be made in this domain. This systematic review analyzes the theoretical advances in sieving that have occurred up to the present. The research followed the PRISMA 2020 guidelines and was conducted using three established databases: Web of Science, IEEE Xplore and Scopus. Our methodical review aims to provide an extensive overview of the progress in prime sieving\u2014unfortunately, no significant advancements in this field were identified in the last 20 years.<\/jats:p>","DOI":"10.3390\/a17040157","type":"journal-article","created":{"date-parts":[[2024,4,15]],"date-time":"2024-04-15T03:56:13Z","timestamp":1713153373000},"page":"157","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Prime Number Sieving\u2014A Systematic Review with Performance Analysis"],"prefix":"10.3390","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-0185-143X","authenticated-orcid":false,"given":"Mircea","family":"Ghidarcea","sequence":"first","affiliation":[{"name":"Computer Science, University Politehnica of Bucharest, Splaiul Independentei 313, 060042 Bucharest, Romania"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3921-5343","authenticated-orcid":false,"given":"Decebal","family":"Popescu","sequence":"additional","affiliation":[{"name":"Computer Science, University Politehnica of Bucharest, Splaiul Independentei 313, 060042 Bucharest, Romania"}]}],"member":"1968","published-online":{"date-parts":[[2024,4,14]]},"reference":[{"key":"ref_1","unstructured":"(2023, February 26). Semantic Scholar. Available online: https:\/\/www.semanticscholar.org\/."},{"key":"ref_2","unstructured":"Nicomachus (1926). Introduction to Arithmetic, Macmillan."},{"key":"ref_3","unstructured":"(2023, February 28). Web of Science. Available online: https:\/\/www.webofscience.com\/."},{"key":"ref_4","unstructured":"(2023, February 27). IEEE Xplore Search Results. Available online: https:\/\/ieeexplore.ieee.org\/."},{"key":"ref_5","unstructured":"(2023, February 27). Scopus. Available online: https:\/\/www.scopus.com\/."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"n71","DOI":"10.1136\/bmj.n71","article-title":"The PRISMA 2020 Statement: An Updated Guideline for Reporting Systematic Reviews","volume":"372","author":"Page","year":"2021","journal-title":"BMJ"},{"key":"ref_7","unstructured":"Harman, G. (2007). Prime-Detecting Sieves, Princeton University Press."},{"key":"ref_8","unstructured":"Crandall, R., and Pomerance, C. (2005). Prime Numbers: A Computational Perspective, Springer."},{"key":"ref_9","unstructured":"Hardy, G.H., Wright, E.M., and Silverman, J.H. (2008). An Introduction to the Theory of Numbers, Oxford University Press. [6th ed.]. Oxford Mathematics."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"13","DOI":"10.4171\/em\/268","article-title":"Euler and the Partial Sums of the Prime Harmonic Series","volume":"70","author":"Pollack","year":"2015","journal-title":"Elem. Der Math."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1090\/S0025-5718-99-01037-6","article-title":"The kth Prime Is Greater Than k(lnk + lnlnk \u2212 1)","volume":"68","author":"Dusart","year":"1999","journal-title":"Math. Comput."},{"key":"ref_12","first-page":"73","article-title":"Sundaram\u2019s Sieve for Prime Numbers","volume":"2","author":"Aiyar","year":"1934","journal-title":"Math. Stud."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1145\/366199.366257","article-title":"Algorithm 35: Sieve","volume":"4","author":"Wood","year":"1961","journal-title":"Commun. ACM"},{"key":"ref_14","first-page":"209","article-title":"Certification of Algorithm 35: Sieve","volume":"5","author":"Brown","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_15","first-page":"438","article-title":"Certification of Algorithm 35: Sieve","volume":"5","author":"Hillmore","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1145\/363566.363689","article-title":"Algorithm 310: Prime Number Generator 1","volume":"10","author":"Chartres","year":"1967","journal-title":"Commun. ACM"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1145\/363566.363692","article-title":"Algorithm 311: Prime Number Generator 2","volume":"10","author":"Charters","year":"1967","journal-title":"Commun. ACM"},{"key":"ref_18","first-page":"563","article-title":"Algorithm 356: A Prime Number Generator Using the Treesort Principle [A1]","volume":"12","author":"Singleton","year":"1969","journal-title":"Commun. ACM"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/362929.362947","article-title":"Letters to the Editor: Go to Statement Considered Harmful","volume":"11","author":"Dijkstra","year":"1968","journal-title":"Commun. ACM"},{"key":"ref_20","first-page":"563","article-title":"Algorithm 357: An Efficient Prime Number Generator [A1]","volume":"12","author":"Singleton","year":"1969","journal-title":"Commun. ACM"},{"key":"ref_21","first-page":"489","article-title":"Remark on Algorithm 357: An Efficient Prime Number Generator [A1]","volume":"16","year":"1973","journal-title":"Commun. ACM"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/359810.359838","article-title":"Some New Upper Bounds on the Generation of Prime Numbers","volume":"20","author":"Mairson","year":"1977","journal-title":"Commun. ACM"},{"key":"ref_23","unstructured":"Pratt, V.R. (1977). CGOL\u2014An Algebraic Notation for MACLISP Users, MIT AI Lab. Working Paper."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1145\/359657.359660","article-title":"A Linear Sieve Algorithm for Finding Prime Numbers","volume":"21","author":"Gries","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1145\/357121.357128","article-title":"An Exercise in Program Explanation","volume":"3","author":"Misra","year":"1981","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/358527.358540","article-title":"A Sublinear Additive Sieve for Finding Prime Number","volume":"24","author":"Pritchard","year":"1981","journal-title":"Commun. ACM"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1007\/BF00264164","article-title":"Explaining the Wheel Sieve","volume":"17","author":"Pritchard","year":"1982","journal-title":"Acta Inform."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/0196-6774(83)90014-7","article-title":"Fast Compact Prime Number Sieves (among Others)","volume":"4","author":"Pritchard","year":"1983","journal-title":"J. Algorithms"},{"key":"ref_29","unstructured":"Sorenson, J. (1990). An Introduction to Prime Number Sieves, University of Wisconsin-Madison, Computer Sciences Department. Technical Report."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Sorenson, J. (1998). Trading Time for Space in Prime Number Sieves, Springer. Technical Report.","DOI":"10.1007\/BFb0054861"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0190(96)00099-3","article-title":"A Space-Efficient Fast Prime Number Sieve","volume":"59","author":"Dunten","year":"1996","journal-title":"Inf. Process. Lett."},{"key":"ref_32","unstructured":"Sorenson, J. (1991). An Analysis of Two Prime Number Sieves, University of Wisconsin-Madison, Computer Sciences Department. Technical Report."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/BF00289493","article-title":"An Incremental Primal Sieve","volume":"23","author":"Bengelloun","year":"1986","journal-title":"Acta Inform."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Pritchard, P. (1994). Improved Incremental Prime Number Sieves, Springer. Technical Report.","DOI":"10.1007\/3-540-58691-1_67"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0167-6423(87)90024-4","article-title":"Linear Prime-Number Sieves: A Family Tree","volume":"9","author":"Pritchard","year":"1987","journal-title":"Sci. Comput. Program."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1090\/S0025-5718-03-01501-1","article-title":"Prime Sieves Using Binary Quadratic Forms","volume":"73","author":"Atkin","year":"2003","journal-title":"Math. Comput."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Galway, W.F. (2000). Dissecting a Sieve to Cut Its Need for Space, Springer. Technical Report.","DOI":"10.1007\/10722028_17"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Farach-Colton, M., and Tsai, M.T. (2015). On the Complexity of Computing Prime Tables. arXiv, Available online: http:\/\/arxiv.org\/abs\/1504.05240.","DOI":"10.1007\/978-3-662-48971-0_57"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01932283","article-title":"The Segmented Sieve of Eratosthenes and Primes in Arithmetic Progressions to 1012","volume":"17","author":"Bays","year":"1977","journal-title":"BIT"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"959","DOI":"10.1090\/S0025-5718-1973-0330021-0","article-title":"The First Occurrence of Large Gaps between Successive Primes","volume":"27","author":"Brent","year":"1973","journal-title":"Math. Comput."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Bokhari (1987). Multiprocessing the Sieve of Eratosthenes. Computer, 20, 50\u201358.","DOI":"10.1109\/MC.1987.1663535"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1006\/inco.1994.1082","article-title":"2 Fast Parallel Prime Number Sieves","volume":"114","author":"Sorenson","year":"1994","journal-title":"Inf. Comput."},{"key":"ref_43","unstructured":"Gabriel Paillard, C.L. (2005, January 4\u20136). A Distributed Prime Sieving Algorithm Based on Scheduling by Multiple Edge Reversal. Proceedings of the 4th International Symposium on Parallel and Distributed Computing (ISPDC\u201905), Lille, France."},{"key":"ref_44","unstructured":"Paillard, G. (2005). A Fully Distributed Prime Numbers Generation Using the Wheel Sieve, Universidade Federal do Cear\u00e1. Technical Report."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Hwang, S., Chung, K., and Kim, D. (2007, January 16\u201319). Load Balanced Parallel Prime Number Generator with Sieve of Eratosthenes on Cluster Computers. Proceedings of the 7th IEEE International Conference (CIT 2007), Aizu-Wakamatsu, Japan.","DOI":"10.1109\/CIT.2007.139"},{"key":"ref_46","first-page":"291","article-title":"Parallelization of Prime Number Generation Using Message Passing Interface","volume":"7","author":"Aziz","year":"2008","journal-title":"WSEAS Trans. Comput."},{"key":"ref_47","unstructured":"Bhukya, D.P., Ramachandram, S., and Sony, A.L.R. (2010, January 28\u201329). Analysis of Sieve of Eratosthenes Method Using MPI Using Statistical DOE Methodology. Proceedings of the IEEE Conference on Computational Intelligence and Computing Research, Coimbatore, India."},{"key":"ref_48","first-page":"192","article-title":"The I\/O Complexity of Computing Prime Tables","volume":"Volume 9644","author":"Kranakis","year":"2016","journal-title":"LATIN 2016: Theoretical Informatics"},{"key":"ref_49","unstructured":"Oliveira E Silva, T. (2023, March 01). Fast Implementation of the Segmented Sieve of Eratosthenes. Available online: https:\/\/sweet.ua.pt\/tos\/software\/prime_sieve.html."},{"key":"ref_50","unstructured":"Oliveira E Silva, T. (2023, March 01). Goldbach Conjecture Verification. Available online: https:\/\/sweet.ua.pt\/tos\/goldbach.html."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"2033","DOI":"10.1090\/S0025-5718-2013-02787-1","article-title":"Empirical Verification of the Even Goldbach Conjecture and Computation of Prime Gaps up to 4\u00b71018","volume":"83","author":"Herzog","year":"2013","journal-title":"Math. Comput."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1145\/321281.321290","article-title":"Generation of Primes by a One-Dimensional Real-Time Iterative Array","volume":"12","author":"Fischer","year":"1965","journal-title":"J. ACM"},{"key":"ref_53","doi-asserted-by":"crossref","unstructured":"Umeo, H., Miyamoto, K., and Abe, Y. (2010, January 2\u20134). A Construction of Smallest Real-Time Prime Generators on Cellular Automata. Proceedings of the 2010 2nd International Conference on Computer Technology and Development, Cairo, Egypt.","DOI":"10.1109\/ICCTD.2010.5645858"},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/BFb0029979","article-title":"Real-Time Generation of Primes by a One-Dimensional Cellular Automaton with 11 States","volume":"Volume 1295","author":"Goos","year":"1997","journal-title":"Mathematical Foundations of Computer Science 1997"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/978-3-319-09039-9_15","article-title":"Real-Time Prime Generators Implemented on Small-State Cellular Automata","volume":"Volume 12","author":"Adamatzky","year":"2015","journal-title":"Automata, Universality, Computation"},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1017\/S0956796804005210","article-title":"FUNCTIONAL PEARL Calculating the Sieve of Eratosthenes","volume":"14","author":"Meertens","year":"2004","journal-title":"J. Funct. Program."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1017\/S0956796808007004","article-title":"The Genuine Sieve of Eratosthenes","volume":"19","year":"2009","journal-title":"J. Funct. Program."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1017\/S0956796811000128","article-title":"A Note on the Genuine Sieve of Eratosthenes","volume":"21","year":"2011","journal-title":"J. Funct. Program."},{"key":"ref_59","unstructured":"Crandall, R.E., and Papadopoulos, J.S. (2023, March 01). On the Implementation of AKS-Class Primality Tests. Available online: https:\/\/api.semanticscholar.org\/CorpusID:14592067."},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/11792086_15","article-title":"The Pseudosquares Prime Sieve","volume":"Volume 4076","author":"Hess","year":"2006","journal-title":"Algorithmic Number Theory"},{"key":"ref_61","doi-asserted-by":"crossref","unstructured":"Tarafder, A.K., and Chakroborty, T. (2019, January 7\u20139). A Comparative Analysis of General, Sieve-of-Eratosthenes and Rabin-Miller Approach for Prime Number Generation. Proceedings of the 2019 International Conference on Electrical, Computer and Communication Engineering (ECCE), Cox\u2019sBazar, Bangladesh.","DOI":"10.1109\/ECACE.2019.8679358"},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"413","DOI":"10.2307\/3611701","article-title":"On Formulae for the Nth Prime Number","volume":"48","author":"Willans","year":"1964","journal-title":"Math. Gaz."},{"key":"ref_63","unstructured":"Kaddoura, I., and Abdul-Nabi, S. (2012). On Formula to Compute Primes and the Nth Prime. arXiv, Available online: http:\/\/arxiv.org\/abs\/1202.4687."},{"key":"ref_64","doi-asserted-by":"crossref","first-page":"352","DOI":"10.1080\/00150517.2017.12427761","article-title":"The Prime Numbers without the Sieve of Eratosthenes","volume":"55","author":"Saidak","year":"2017","journal-title":"Fibonacci Q."},{"key":"ref_65","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BFb0054860","article-title":"Robert Bennion\u2019s \u201cHopping Sieve\u201d","volume":"Volume 1423","author":"Goos","year":"1998","journal-title":"Algorithmic Number Theory"},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1112\/S1461157015000194","article-title":"Two Compact Incremental Prime Sieves","volume":"18","author":"Sorenson","year":"2015","journal-title":"LMS J. Comput. Math."},{"key":"ref_67","unstructured":"Farhadi, B., and Farhadi, B. (2015, January 28\u201331). A New Algorithm for Prime Number Production: Usable in Computer Cryptography Communication Systems. Proceedings of the Electronics Information & Planning, Singapore. Available online: https:\/\/www.researchgate.net\/publication\/283948996_A_new_algorithm_for_prime_number_production_usable_in_computer_Cryptography_communication_systems."},{"key":"ref_68","unstructured":"Prasad Rao, B. (2017). A Sieve to Find Prime Numbers below 2n for given Natural Number n, ResearchGate Preprint."},{"key":"ref_69","doi-asserted-by":"crossref","first-page":"030019","DOI":"10.1063\/1.5097530","article-title":"An Algorithm and a Sieve to Find Prime Numbers below 2n for given Natural Number n","volume":"2095","author":"Rao","year":"2019","journal-title":"AIP Conf. Proc."},{"key":"ref_70","unstructured":"Helfgott, H.A. (2019). An Improved Sieve of Eratosthenes. arXiv, Available online: http:\/\/arxiv.org\/abs\/1712.09130."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/4\/157\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T14:27:52Z","timestamp":1760106472000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/17\/4\/157"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,14]]},"references-count":70,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,4]]}},"alternative-id":["a17040157"],"URL":"https:\/\/doi.org\/10.3390\/a17040157","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,14]]}}}