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

**Download 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

- Abramowitz, M., & Stegun, I. A. (1970).
*Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables*. Dover Publications, New York. - Apostol, T. (1976).
*Introduction to Analytic Number Theory*, Undergraduate Texts in Mathematics, Springer-Verlag. - Atkins, A. O. L., & Bernstein, J. (2004). Prime Sieves using Binary Quadratic Forms.
*Mathematics of Computation*, 73(246), 1023–1030. - Cox, D. N. (2008). Visualizing the Sieve of Eratosthenes.
*Notices of the American Mathematical Society*, 55(5), 579–582. - 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. - 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. - Gronwall, T. H. (1913). Some asymptotic expressions in the theory of numbers.

*Transactions of the American Mathematical Society*, 14, 113–122. - Hardy, G. H., & Wright, E. M. (2006).
*An Introduction to the Theory of Numbers*, 6th edition. Oxford University Press. - Hinz, J. G. (2003). An application of algebraic sieve theory.
*Archiv der Mathematik*, 80, 586–599. - 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. - Nathanson, M. B. (2000).
*Elementary Methods in Number Theory*. Springer-Verlag, New York. - 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. - Tytus, J. B. (2004).
*The Random Sieve of Eratosthenes*, Science Direct Working Paper No S1574-0358(04)70421-9. - 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. - 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

## Related papers

## Cite this paper

Cotronei, A. (2022). On wide-output sieves. *Notes on Number Theory and Discrete Mathematics*, 28(2), 147-158, DOI: 10.7546/nntdm.2022.28.2.147-158.