On wide-output sieves

Alessandro Cotronei
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 28, 2022, Number 2, Pages 147–158
DOI: 10.7546/nntdm.2022.28.2.147-158
Full paper (PDF, 282 Kb)

Details

Authors and affiliations

Alessandro Cotronei
Department of Mathematics and Statistics, University of Tromsø
N-9037 Tromsø, Norway

Abstract

We describe and compare several novel sieve-like methods. They assign values of several functions (i.e., the prime omega functions ω and Ω and the divisor function d) to each natural number in the considered range of integer numbers. We prove that in some cases the algorithms presented have a relatively small computational complexity. A more detailed output is indeed obtained with respect to the original Sieve of Eratosthenes.

Keywords

• Sieve theory
• Sieve of Eratosthenes

2020 Mathematics Subject Classification

• 11N35
• 11N36

References

1. Abramowitz, M., & Stegun, I. A. (1970). Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. Dover Publications, New York.
2. Apostol, T. (1976). Introduction to Analytic Number Theory, Undergraduate Texts in Mathematics, Springer-Verlag.
3. Atkins, A. O. L., & Bernstein, J. (2004). Prime Sieves using Binary Quadratic Forms. Mathematics of Computation, 73(246), 1023–1030.
4. Cox, D. N. (2008). Visualizing the Sieve of Eratosthenes. Notices of the American Mathematical Society, 55(5), 579–582.
5. Da Costa, C. M. C., Sampaio, A., & Barbosa, J. G. (2014). Distributed Prime Sieve in Heterogeneous Computer Clusters. Proceedings of the 14th International Conference on Computational Science and Its Applications, Lecture Notes in Computer Science, Vol. 8582. Springer, Cham, 592–606.
6. De Saint Guilhem, C. D., Makri, E., Rotaru, D., & Tanguy, T. (2021). The Return of Eratosthenes: Secure Generation of RSA Moduli using Distributed Sieving. Proceedings of 2021 ACM SIGSAC Conference on Computer and Communications Security, 594–609.
7. Gronwall, T. H. (1913). Some asymptotic expressions in the theory of numbers.
   Transactions of the American Mathematical Society, 14, 113–122.
8. Hardy, G. H., & Wright, E. M. (2006). An Introduction to the Theory of Numbers, 6th edition. Oxford University Press.
9. Hinz, J. G. (2003). An application of algebraic sieve theory. Archiv der Mathematik, 80, 586–599.
10. Li, B., Maltese, G., Costa-Filho, J. I., Pushkina, A. A., & Lvovsky, A. I. (2020). Optical Eratosthenes’ sieve for large prime numbers. Optics Express, 28(8), 11965–11973.
11. Nathanson, M. B. (2000). Elementary Methods in Number Theory. Springer-Verlag, New York.
12. Sorenson, J. (1990). An Introduction to Prime Number Sieves, Computer Sciences Technical Report N. 909, Department of Computer Sciences, University of Wisconsin-Madison, January 2, 1990.
13. Tytus, J. B. (2004). The Random Sieve of Eratosthenes, Science Direct Working Paper No S1574-0358(04)70421-9.
14. Ufuoma, O. (2019). A New and Simple Prime Sieving Technique for Generating Primes Ending with a Given Odd Digit. Asian Research Journal of Mathematics, 15(5), 1–11.
15. Weisstein, Eric W. Distinct Prime Factors. From MathWorld–A Wolfram Web Resource. https://mathworld.wolfram.com/DistinctPrimeFactors.html

Manuscript history

• Received: 9 November 2021
• Revised: 17 February 2022
• Accepted: 9 March 2022
• Online First: 23 March 2022