The standard procedure to construct prime numbers is the sieve of Eratosthenes. If one wishes to find prime numbers upto a given positive integer N, one starts with the set {2, 3, 4, 5, 6, …, N}. Leave 2 and mark all the multiples of 2. Apply the same procedure to 3, and continue. One is left with the set of primes.

In the sieve of Eratosthenes, when one starts with 2, it is already assumed that 2 is a prime. Our method is a refinement of the sieve of Eratosthenes. First, we algebraically prove that 2 is a prime and then cancel all its multiples in the set given above. Then we prove that 3 is a prime and cancel all its multiples and so on.

prime numbers, sieve of Eratosthenes, consecutive integers, co-primes, fundamental theorem of arithmetic.

Received: April 25, 2021; Accepted: May 18, 2021; Published: May 25, 2021

How to cite this article: Shahid Nawaz and Almas Khan, A note on the sieve of Eratosthenes, Far East Journal of Mathematical Education 21(1) (2021), 79-82. DOI: 10.17654/ME021010079

This Open Access Article is Licensed under Creative Commons Attribution 4.0 International License

References:

[1] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 6 ed., Oxford University Press, Oxford, 2008.
[2] T. M. Apostol, Introduction to Analytic Number Theory, Springer, New York, 1976.