An Introduction to Prime NumbersWhat are they?A number (greater than 1) is a prime number if has no positive divisors (factors) except for 1 and itself. For example, 3 is prime because its divisors are 1 and 3 only. But 4 is not a prime, because it's divisors are 1, 2 and 4.
Why are they important?Prime numbers can be thought of as the "building blocks" of the whole numbers. Every number is built out of prime factors, just as every molecule is built out of atoms. The "Fundamental Theorem of Arithmetic", established by Euclid, says that: Every integer greater than 1 is either prime itself or is the product of prime numbers. Although the order of the primes in the product is arbitrary, the primes themselves are not. We have already used this theorem: In the first mini-challenge, we saw that the total number of divisors is related to the (unique) prime factorization in a simple way. Why are they mysterious?Prime numbers are rather mysterious, and they have intrigued mathematicians through the ages. Here are some aspects of their mystique:
Computing the Prime NumbersSuppose we want to compute all the prime numbers less than N. How can we do it? Well, a simple but effective method was first introduced by Eratosthenes, in the third century BC. The Sieve of EratosthenesFirst, write out the numbers from 1 to N. You can write them in a line, or in a square like this (for the numbers 1 to 100):  First, strike out ("cross out") 1, because 1 is not a prime. Then, strike out all the even numbers except for 2 itself ... because all even numbers greater than 2 divide by two, so cannot be prime. Next, find the smallest number which has not been struck out, i.e., 3. Now strike out every multiple of 3 (except 3 itself), i.e. every third number. Moving on, we find that 4 has been eliminated, but 5 has not. So we strike out all multiples of 5 (except 5 itself), and move on again, repeating in this fashion. Continue until you have eliminated all the composite numbers. The numbers that remain are the primes! You may have a grid that looks something like this:  This grid shows that 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 are prime. You may have noticed that all composite numbers in the grid above (the crossed-out numbers) are divisible by 2, 3, 5 or 7. These are the primes which are less than the square root of 100, i.e. 10. In other words, it was only necessary to strike out the powers of 2, 3, 5 and 7 to complete the task for N=100. Can you see why this is? (Hint: The smallest composite number that is not divisible by 2, 3, 5 or 7 is 11 x 11 = 121). Writing an algorithmErathosthenes' sieve works by repeating a set of simple steps: it is one of the very first examples of an algorithm. Computers are excellent at implementing algorithms, as they work extremely fast and do not seem to get bored! Let's consider how we could make the Sieve of Erathosthenes work in a computer code. First, we could write the steps in the algorithm out in words:
Let's start with steps 1 to 3. We want to strike out the multiples of 2 by setting them to zero. But how can we keep track of whether a number has been struck out or not? One way is to use a list ( a, say) with n+1 elements, representing the status of numbers 0 to n. We will strike out a number (i, say) by setting a[i] equal to 0. Let's try writing some lines of code to do this:n = 10000 # Set the size of the sievea = [1]*(n+1) # list of length n+1, every element equal to 1 (not crossed out)p = 2 # 2 is the first primej = 2*p # This is the first multiple of pwhile j <= n: # a loop which continues until we exceed the size of the sieve a[j] = 0 # "cross out" the multiple by setting a[j] equal to zero j += p # move on to the next multiple of pDo you understand the steps here? Here are some observations:
Try entering these lines in a Python module, save the file, and run it (for instructions, see Tutorial 1). If it doesn't work, you'll see some kind of error message -- can you fix the code? (First, check that the indenting has been copied correctly). If it works, then you should see a list of 1s and 0s, with all the multiples of two set equal to 0. The next task is to implement step 4: moving on through the list to find the next prime number. This could also be achieved with another "while" loop: p += 1 # Step forward oncewhile a[p] == 0: p += 1 # Keep stepping forward until we reach the end of the loopThese lines are a little bit dangerous: what happens if p increases until it exceeds n? Then we will fall off the end of the list, and the program will "throw an error". This error will crash your program (unless it is "caught")! To stop this happening, we we need to think a bit more carefully about how to terminate the program once it's job is done. In other words, how to stop once p exceeds the square root of n.To make the whole algorithm work, we need to iterate the process of crossing out prime multiples, and moving forward to get the next prime p. But we need to stop when the prime counter p exceeds the square root of n. Can you work out how to do this? Try writing a program to implement Eratosthenes' Sieve algorithm in full. If you can do this, congratulations -- you are well on your way to becoming a mathematical programmer! If not, don't worry, take a look at the first Python file ( sieve1.py) attached to this page. Can you see how it works? Try it!Extending your programOnce you have a working algorithm for finding all the prime numbers less than N, using the Sieve of Eratosthenes, you can use it in many ways. If you are feeling confident, you may like to skip to the Exercises below. On the other hand, you may be more interested in improving your program in other ways. For example, you could:1. Improve the program so that it asks the user to enter the size of the sieve. You could use the following line: str = raw_input("What is the size of the sieve?")n = int(str)This is OK, as long as the user enters an whole number greater than 2. But if they enter "what do you mean?", the program will throw an error, and crash! So, it would be a good idea to check the user's input, to make sure it is valid for the program. If not, you can give the user some gentle instructions. 2. Test the efficiency of the sieve algorithm. In other words, how long does it take to run? Of course, this depends on the size of the sieve, and the speed/memory of your computer. I would expect the time taken by the algorithm to increase (very roughly) in proportion to n. 3. Use the list of primes to look for factors of, e.g., the Mersenne numbers 2n - 1, and the Fermat numbers. If you are feeling confident, try making enhancements 1, 2 and 3 for yourself. If you are not sure how to get started, take the second code at the foot of the page, sieve2.py,. This gives some example Python code. Take a look, to see if you can follow the logic. (If it doesn't work, let me know: pi3challenge@sheffield.ac.uk). Graphics and animationsThe Sieve of Eratosthenes' has been studied through the ages -- so we are in good company! On the Wikipedia page, you will find a rather nice animation showing how the sieve filters out composite numbers, in a step-by-step manner.Next week we will write a Python program to illustrate how we may apply the sieve to the first 10000 numbers. It will look something like this:  ExercisesUsing a list of primes that you found with the Sieve of Eratosthenes, can you answer the following questions:
|
Tutorials >
, whose value is equal to the number of primes less than or equal to x. It is known that the number of primes less than x is roughly equal to x / log(x), when x is large. But on the small scale, the primes seem to be scattered somewhat "randomly". Efforts to understood their distribution have created unexpected links with other areas of mathematics (see e.g. 