site map

sums will set you free

how to teach your child numbers arithmetic mathematics

prime numbers and factors,
the sieve of Eratosthenes

• prime numbers and factors, the sieve of Eratosthenes
• the sieve of Eratosthenes
• an example of using an Eratosthenes’ sieve, for numbers from 1 to 200
• LCM - lowest common multiple
• HCF - highest common factor

prime numbers and factors, the sieve of Eratosthenes

A prime number is a number (other than one) that is divisible only by 1 and by itself [1]. Its factors are then one and that prime number. A prime number is also a number that cannot be divided any further.

However, the number one needs to be paid little attention as multiplying any integer[2] by one leaves the integer unchanged. Thus two times one equals two (2 x 1 = 2), one hundred and fifty-seven multiplied by one equals one hundred and fifty-seven (157 x 1 = 157), and one million, eight hundred and twenty-four thousand four hundred and one multiplied by one remains that big number (1,824,401 x 1 = 1,824,401).

Dividing by one, likewise, leaves the integer unchanged. So one hundred and forty-three divided by one remains as one hundred and forty-three (143 ÷ 1 = 143). Forty-two times one times one times one still remained forty-two (42 x 1 x 1 x 1 = 42), as does forty-two times one times one times one divided by one (42 x 1 x 1 x 1 ÷ 1 = 42). Caution: this behaviour tends to come unstiched with the ‘number’ zero, otherwise known as nothing. Doubtless, zero will raise its ugly little non-existent head again in due course.

The factors (of a number) are the prime numbers that multiply up to make the number concerned. For instance, the number 10 has the factors 1, 2 and 5. That is, one times two times five makes ten. 1 x 2 x 5 = 10. But from now on, we shall ignore the one, and so we list the factors of 10 as 2 and 5, or 2 by 5, 2 x 5.

Another example is the factors of 12, which are 2, 2, 3, as in 2 x 2 x 3 = 12.

the sieve of Eratosthenes [2]

Here follows the method of Eratosthenes’ sieve to determine prime numbers up to 200. Of course, if you wish, you can continue and determine prime numbers of greater value than those shown here. Below is a table of numbers from 1 to 200 that will be used for the 'sieving' process illustrated a bit further dowb this page.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100
101	102	103	104	105	106	107	108	109	110
111	112	113	114	115	116	117	118	119	120
121	122	123	124	125	126	127	128	129	130
131	132	133	134	135	136	137	138	139	140
141	142	143	144	145	146	147	148	149	150
151	152	153	154	155	156	157	158	159	160
161	162	163	164	165	166	167	168	169	170
171	172	173	174	175	176	177	178	179	180
181	182	183	184	185	186	187	188	189	190
191	192	193	194	195	196	197	198	199	200

Click to see a blank number sheet for printing out. [Opens in new tab/window.]
This sheet can be used by the learner for practicing with an Eratosthenes’ sieve. This enhances experience with how times tables work.

With an Eratosthenes’ sieve, the multiples of each prime number are progressively crossed out of the list of all numbers being examined (in this case the numbers one to two hundred, 1 to 200). You will notice that by the time you come to crossing out the multiples of three, several have already been crossed out: 6, 12, 18 etc.

The blank sheet can, of course, be used for an exercise in crossing out other series alone, such as just threes, as well as non-primes, such as fours or sixes.

an example of using an Eratosthenes’ sieve
for numbers from 1 to 200

The first prime number other than one is two (2). All multiples of two are crossed off the table (here we have used red for two and its multiples). Thus the sieve has removed all the non-primes which are divisible by the prime number two. The sieve removes non-primes and what will eventually be left in the sieve will be the remaining prime numbers.

Sieving out the prime numbr 2 and its multiples

advertising disclaimer

The next prime number is three (3). Here its multiples are crossed off in blue, unless they have already been crossed out as a multiple of two. Now the sieve has removed all the non-primes which are divisible by the prime numbers two and three. Thence the process continues.

Sieving out the prime numbr 3 and its multiples

Five is the next prime number. Multiples of five are crossed off in green, unless they have already been crossed out.

Sieving out the prime numbr 5 and its multiples

The next prime number is seven. Its multiples are crossed out in orange, unless previously crossed.

Sieving out the prime numbr 7 and its multiples

Below, all further prime numbers have been outlined in purple. The purple crossed out numbers are multiples of prime numbers greater than seven.

Sieving out the other multiples of prime numbers from numbers up to 200

You will see that, when you come to the seventeens (17), all non-primes have already been crossed out [34, 51, 68, 85, 102, 119, 136, 153, 170, 187]. That leaves the primes uncrossed and they are highlighted above with coloured boxes.

Of the ’teen numbers before seventeen, note that 13 x 13, 13², is already 169, while 13 x 14 is 182, 13 x 15 is 195, and 13 x 16 exceeds 200, which is as far as this table goes. 13 x 17 is 221, well beyond our table’s upper limit. 14, 15, 16 have already been crossed off the table because they are divisible by earlier prime numbers. (14 = 2 x 7, 15 = 3 x 5, 16 = 2 x 2 x 2 x 2.)

The full list of prime numbers from 1 to 200 is:

1	2	3	5	7	11	13	17	19	23
29	31	37	41	43	47	53	59	61	67
71	73	79	83	89	97	101	103	107	109
113	127	131	137	139	149	151	157	163	167
173	179	181	191	193	197	199

LCM - lowest common multiple

To understand the idea of Lowest Common Multiple - LCM, first you need you understand what is a multiple.

When a particular whole number is multiplied by any other whole number, the resulting number (the result) is a multiple of the number you first thought of.

For example, with the number three (3), 3 is its first multiple because 3 x 1 = 3.
Three’s second multiple is 6: 3 x 2 = 6.
The first five multiples of three are 3 x 1 = 3, 3 x 2 = 6, 3 x 3 = 9, 3 x 4 = 12, 3 x 5 = 15.
Listed, the first five multiples of three are 3, 6, 9, 12, 15.

This list of multiples, and the following multiples of three, can be seen easily using a multiplication cross table.
Below are highlighted the first ten multiples of three.

common multiples

The shared or common multiples of two numbers are the numbers which are multiples of both numbers.

To find the common multiples of, say, 8 and 12, you first list multiples of each number:
8, 16, 24, 32, 40, 48 ......
12, 24, 36, 48 .....

On the following cross table, common factors of 8 and 12 are highlighted in crimson.

So common multiples of 8 and 12 are 24, 48, 72, 96 and so on.

The lowest common multiple is the smallest multiple of a pair, or a group, of numbers. So for the pair of numbers, 8 and 12, the lowest common multiple is 24. The LCM can also be seen as the smallest number into which both (or all) numbers will divide.

HCF - highest common factor

To understand the idea of Highest Common Factor - HCF, first you need you understand what is a factor.

As was explained previously, the factors (of a number) are the prime numbers that multiply up to make the number concerned.

For instance, the number 10 has the prime factors 1, 2 and 5. That is, one times two times five make ten. 1 x 2 x 5 = 10. We shall continue to ignore the one, and so we list the prime factors of 10 as 2 and 5, or 2 by 5, 2 x 5.

common factors

When two or more numbers have the same factor, that factor is called a common factor. For instance, to find the common factors of 8 and 12, you first list the prime factors to be found in each of those numbers:

The prime factors of 8 are 2, 2 and 2 (evidenced by the equation 2 x 2 x 2 = 8).
The prime factors of 12 are 2, 2 and 3 (evidenced by the equation 2 x 2 x 3 = 12)

Now, the highest common factor is the biggest number that will divide into a pair, or a group, of numbers, without leaving a remainder.
In other words, the HCF is the biggest of all the common factors (whether prime or composite) of the numbers concerned.

As you can see in the example above, the common prime factors of 8 and 12 are 2 and 2. Note carefully, both our original numbers, 8 and 12, have in common two lots of the factor 2. When multiplied together, two times two equals four, 2 x 2 = 4, these prime factors make a composite common factor: 4. So the highest common factor of 8 and 12 is 4.

However, to find the highest common factor of two or more numbers, some people prefer to use the method of looking for all the factors of those numbers, not just the prime factors. But you must be aware, that although this method works well with smaller numbers that have fewer and smaller factors, it is hopeless for larger numbers which you cannot easily deconstruct into all their factors. For those larger numbers, it will be necessary to return to basics, as described above, and determine the prime factors concerned, and then multiply those back up as necessary.

Using the method of looking for all the factors in a number:

For 8, all its factors are 2, 4, 8. (The factor 4 is made from 2 x 2, the factor 8 is made up from 2 x 2 x 2.)
For 12, all its factors are 2, 3, 4, 6, 12. (The factor 4 is made from 2 x 2, the factor 6 from 2 x 3, the factor 12 from 2 x 2 x 3.)

Thus, the common factors of 8 and 12 are 2 and 4, so the highest common factor of 8 and 12 is 4.

Web abelard.org

end notes

1. Prime numbers are useful in various applications, but there is no known formula for deriving them. Many number theorists have sweated blood and substantial periods of their lives trying to find useful theories of primes. Now much of that game has been taken up by computers, which are much faster and, in general, far more reliable. The reality is that prime numbers are mostly detected by struggling to divide a number into them and failing. This is not something that I would advise worrying your pretty little head over, let alone impose upon a youngster learning mathematics.
   
   The best thing is to be thankful for the usefulness of prime numbers and grab them in your shopping as you go past. One useful definition of a prime number is a number which can be divided only by two numbers - itself and the number one (1). That is at least a neat way of removing one from the list of primes; for one, like zero, can be an awkward and embarrassing little brat.
   
   Prime numbers, essentially, are established by empiric (experimental) means such as Eratosthenes’ sieve. This is done for practical purposes such as adding together recalcitrant fractions, as we are preparing here, and, a few miles down the road, for generating useful encryption methods.
   
   
2. Integers are whole numbers, but definitions can vary according to purpose. Sometimes reference is made to the ‘natural numbers’, these being only the positive integers, or the non-negative integers. When called non-negative integers, zero is included.
   
   
3. Eratosthenes [c.276 BC– c. 195 BC] was a Greek mathematician in ancient times, and a friend of Archimedes. Eratosthenes is known for his work with prime numbers, and developing the Sieve of Eratosthenes for determining prime numbers. He also measured the circumference of the Earth accurately, as well as the distance of the sun and the moon from the Earth. He also created the first calendar that included leap years.
   
   
4. Whereas a prime number is only divisible by one and itself, a composite number can be divided by more than just two different numbers. So 6 is a composite number, made up, or composed, of the prime numbers (1 x) 2 x 3, while 18 is another, being made from (1 x) 2 x 3 x 3.

email email_abelard [at] abelard.org

© abelard, 2009,12 september

all rights reserved

the web address for this page is https://www.abelard.org/sums/teaching_number_arithmetic_mathematics_factors_primes.php

1300 words
prints as 9 A4 pages (on my printer and set-up)