Listing All the Composite Numbers

The Sieve of Eratosthenes is a process of the gradual elimination of composite numbers from a list of all positive integers. First one removes all the multiples of 2, then all the multiplies of 3, and so on. The prime numbers are the ones that remain.

Curiously enough, it is possible to arrange all the composite numbers in a table with a single swoop and not by a step-by-step process. In this case the prime numbers are those that have been left over.

The applet below shows one playful approach to accomplishing this task.

With the "Show n" box checked, the applet displays a table of integers that are arranged according to the following rules:

1. The first row contains the terms of the arithmetic series 4, 7, 10, 13, ..., i.e., the numbers computed from the formula 4 + 3k, k = 0, 1, 2, ...,

2. These same numbers are listed in the first column,

3. Each subsequent row displays an arithmetic sequence with a difference that is increased by 2: the second row has the difference 5, the third 7, and so on.

With this arrangement, we can make a statement.

Theorem

An integer x > 2 is prime if and only if the number n = (x - 1) / 2 does not appear in this table.

To see why this is true, check the "Show x" box. The numbers that will be displayed are obtained from x = 2n + 1, with n's in the previous table. What do you see?

---

If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

---

What if applet does not run?

When the box "Show x" is checked, the table displays all the odd composite numbers. The first row contains the multiples of 3, the second of 5, the third of 7, and so on. Missing are the even number which are all composite any way (except for 2, of course) and all odd primes. All other numbers are in the table.

More accurately, the first row consists of all odd multiples of 3 (except 3), the second of all odd multiples of 5, and so on.

References

1. C. S. Ogilvy and J. T. Anderson, Excursions in Number Theory, Oxford University Press, 1966, 98-99

Related material Read more...
	Sieves
	Geometric view of the Sieve of Eratosthenes
	Lucky Numbers
	Sieve of Eratosthenes
	Sieve of Squares
	The Parabolic Sieve of Prime Numbers

|Contact| |Front page| |Contents| |Arithmetic|

Copyright © 1996-2018 Alexander Bogomolny