I would appreciate it if you could share with me any algorithm to determine whether a number is prime. Also, could you let me know what is the importance of the study of prime numbers in mathematics. Thanks,

It is difficult to know at what level you are asking this question. I will assume therefore that you are working with children (there are extremely complex and sophisticated techniques in existence but they require graduate level mathematics to understand them).

Usually with children we start with what is called the "Sieve of Eratosthenes". For example, make a 10 by 10 grid and place 1 to 10 in the first row, 11 to 20 in row two, etc., until you get to 100. To find the primes less than or equal to 100,

• Cross out the number 1
• Cross out all the multiples of 2 except 2 itself (4,6,8, ...).
  The smallest remaining number is 3.
• Cross out all the multiples of 3 except 3 itself in what remains.
  The smallest remaining number is 5.
• Cross out all the multiples of 5 except 5 itself in what remains.
  The smallest remaining number is 7.
• Cross out all the multiples of 7 except 7 itself in what remains.

The above gives the basis for a simple algorithm to check to see if a number is prime -- simply try to divide it by each of the small primes up to its square root. If none divide it, it is prime. Why isn't this a good algorithm in general? It requires knowledge of all the primes up to its square root. So if we wanted to know is (2^11213)-1 is prime, using this algorithm we would need to know primes 2,3,5, .... up to primes of the order (2^5606) for example.

Eratosthenes (ca. 284-192 B.C.) spent much of his life as the chief librarian at the great Library at Alexandria. He wrote works in pure mathematics, philosophy, geography and astronomy. He was a highly respected scholar, in fact Archimedes, a contemporary of Eratosthenes, dedicated at least one work to him. Probably Eratosthenes' best known scientific achievement was a determination of the circumference of the earth.

Mathematicians are interested in the prime numbers because they form the building blocks for the natural numbers in the same way that atoms form the building blocks for more complex molecules. Every natural number can be factored into a product of prime numbers, the prime numbers being the indivisible "atoms" of our number system. One of the most useful applications of large prime numbers is in the construction of secret codes. These codes are based on numbers that are the product of two very large prime numbers. The reason such codes are very difficult to break is that there is no quick method for finding the prime factors of large numbers. It is extremely unlikely that anyone will discover a fast method. Modern methods for finding prime factors are only slightly better than the method of checking all possible divisors. A thousand digit number may require hundreds of years of computing to find its prime factors. There is little work involved in the encoding and decoding of the message because both of these people know one of the prime factors. Not only is the secure transmission of information essential for national security, but it is also important for banks and large corporations.

Penny Nom