# prime numbers and factors, the sieve of Eratosthenes how to teach your child number arithmetic mathematics - prime numbers and factors, the sieve of Eratosthenes is part of the series of documents about fundamental education at abelard.org. These pages are a sub-set of sums will set you free

 how to teach a person number, arithmetic, mathematics on teaching reading

## 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 . 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 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 

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

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, 132, 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.

 0 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 2 2 4 6 8 10 12 14 16 18 20 3 3 6 9 12 15 18 21 24 27 30 4 4 8 12 16 20 24 28 32 36 40 5 5 10 15 20 25 30 35 40 45 50 6 6 12 18 24 30 36 42 48 54 60 7 7 14 21 28 35 42 49 56 63 70 8 8 16 24 32 40 48 56 64 72 80 9 9 18 27 36 45 54 63 72 81 90 10 10 20 30 40 50 60 70 80 90 100

### 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.

 0 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 3 4 5 6 7 8 9 10 11 12 2 2 4 6 8 10 12 14 16 18 20 22 24 3 3 6 9 12 15 18 21 24 27 30 33 36 4 4 8 12 16 20 24 28 32 36 40 44 48 5 5 10 15 20 25 30 35 40 45 50 55 60 6 6 12 18 24 30 36 42 48 54 60 66 72 7 7 14 21 28 35 42 49 56 63 70 77 84 8 8 16 24 32 40 48 56 64 72 80 88 96 9 9 18 27 36 45 54 63 72 81 90 99 108 10 10 20 30 40 50 60 70 80 90 100 110 120 11 11 22 33 44 55 66 77 88 99 110 121 132 12 12 24 36 48 60 72 84 96 108 120 132 144

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. Web abelard.org
 sums will set you free includes the series of documents about economics and money at abelard.org. moneybookers information e-gold information fiat money and inflation calculating moving averages the arithmetic of fractional banking :: click to select documents about economics and money :: The mechanics of inflation – the great government swindle and how it works EMU (European Monetary Union) and inflation Corporate corruption, politics and the 'law' GDP and other quality of life measurements Transfering value (money) using the internet e-gold: a developing example of an independent monetary system Moneybookers, a non-gold based value transfer system PayPal and Billpoint - more detailed information The sum of a geometric sequence : the arithmetic of fractional banking Calculating moving averages

 You are here: how to teach your child number arithmetic mathematics - prime numbers and factors, the sieve of Eratosthenes < sums will set you free < Home

 about abelard memory, paranoia & paradigms francis galton france zone memory & intelligence loud music & hearing damage children & tv violence information abstracts briefings news headlines news archives latest