ÿþ<html> <head> <title>MM of Everything: The Sieve of Eratosthenes</title> <style><!--a:hover{color:FF2222; }--></style> </head> <body bgcolor="#99FFFF" text = "#4400AA" link="#008000" alink="#008000" vlink="#008000" > <meta name="keywords" content="Kjartan, Poskitt, Kjartan Poskitt, Murderous Maths, Murderous maths of everything, Eratosthenes,"> <meta name="description" content="The Murderous Maths Sieve of Eratosthenes"> <H1> <a href="../../indextxt.htm"> <img src="mmlogonew2.gif" align=LEFT hspace=20 border=0></A> <a href="../MMoE.htm"> <IMG SRC="MMoEcovsm.jpg" align=right border=0></A> <font color ="#ee0000">The <i>Murderous Maths</i> Sieve of Eratosthenes</FONT></H1> <P CLEAR=LEFT> <a href="greekgeeks.htm"> <img src="eratstatue.gif" align=left border=0></a> <P>In <a href="../MMoE.htm">The Murderous Maths of Everything</A> we meet several ancient Greek mathematicians including <B>ERATOSTHENES</B>. Eratosthenes did lots of rather neat things, but he's best known for his method of finding <a href="../../games/primcal.htm">prime numbers</A>. This is called the Sieve of Eratosthenes. <P>This is our version of the sieve as it appears in the book, but here we're going to show you a couple of extra details that the book didn't have space for. <P>We're going to find all the prime numbers up to 100. We start by writing them out in a square grid, and then we work along the numbers and  sieve out all the numbers that are not prime. <P><img src="new sieve.gif" align=right> <P> <UL> <LI>The first number is 1 but we ll ignore it because when it comes to prime numbers, 1 is a naughty little number who just causes arguments. <LI>Move on to the next number after 1 which is 2. We put a nice little <font color="00cc00"><b>green</b></font> box around it. We then go through and colour in every second number that comes after it. (i.e. all the numbers that divide by 2.) <LI>The next number after 2 is 3, and as it hasn t been coloured in, that means it s also a prime number. We put a <font color="0022FF"><b>blue</b></font> box around the 3 and colour in every third number after it that isn't already coloured. (You ll find the lowest number we colour is 3 × 3 = 9) <li>After 3 the next number is 4 but that s already been coloured in which means it isn't prime. So we move on to 5, we put an <font color="DD9900"><b>orange</b></font> box round it and colour every 5th number after it. (The lowest number we colour is 5 × 5 = 25) <li>The next unmarked number is 7 so we box it in <font color="BB22BB"><b>purple</b></font> and colour in every 7th number. (Yes, 7× 7 = 49 is the lowest!) <li>We have now finished the top row of the square. This means that all the numbers up to 100 that are NOT primes are coloured in, and all the prime numbers are either boxed or left blank. </ul> <P><b>Why don't we need to work beyond the top row of the square?</b> If we move on to the next unmarked number, we find it's 11. If we boxed it and then tried to colour the first unmarked number that divides by 11, that would be 11 x 11 = 121. This is bigger than 100 so we don't need it! That's why we started out by putting our numbers in a square. Once we've finished working along the top row, we can be confident that it's time to stop! <P><b>Why did we ignore the number 1?</b> In the book you'll see how the <b>EVIL NUMBER 1</b> causes all sorts of problems, especially with prime numbers. If we boxed the number 1 then coloured in every number that divides by 1, we'd end up colouring in ALL the numbers! That wouldn't get us very far so that's why we ignored it. <P clear=right><img src="new 200 sieve.gif" align=right> If you wanted to find all the primes up to 200, you need to make a square measuring 15 x 15. (This will actually give you all the primes up to 225.) You just work along the top row in the same way, and when you've finished all the primes will be revealed! <P>If you like numbers (and some people do!) it's interesting to see the odd little patterns that emerge when you make these grids. Here you'll notice how the green "2" boxes form a chequerboard pattern and how the purple "7" boxes are all in diagonals... <P>...<font size = 4><B>but</B></font> the thing that has been bothering mathematicians for thousands of years is that it doesn't matter how the number grid is laid out, they can't make the white prime boxes fall into ANY kind of pattern! <P> <P> <P><BR> <img src="mmlogonew2.gif" ALIGN=LEFT> <FONT FACE = "ARIAL"> <P><a href="../MMoE.htm" > The Murderous Maths of Everything</a> <P><a href="../../games/primcal.htm">The Prime Number Calculator</A> <P><a href="../primeflash/index.htm">The Prime Counter</A> <P><a href="../../indextxt.htm" > Murderous Maths Home Page</a> </body> </html>