Prime Numbers

Prime numbers have long been an interest of mine. The main reason is that with large numbers it takes a very long time to reliably decide whether that number is prime or not. This gives rise to more creative methods being devised. Interest in this area is heavily funded from the cryptography because large prime numbers play a key role in the development of encryption (secure, coded) systems.

Here is a simple Java applet which allows you to type in a number and find out whether or not it is prime:

Prime Number Test

[ Sorry, you cannot see the applet because your browser does not support Java applets ]

source:  Prime Numbers

A prime number is one which cannot be expressed as a product of two whole numbers other than itself and 1. For example, 6 equals 2 times 3, so 6 is not prime. 7 is a prime number because only 1 and 7 can be multiplied together to give 7.

The applet above simply checks all whole numbers from 2 up to the square root of the number to see if any of them divide evenly into the number being tested. Both the interface and the core algorithm could do with some work.

Some of the imaginative methods people have used to see if a number is prime or not include:

• just check whole numbers from 2 up to the square root of the number you are testing - if it has any factors, one of them must be less than its square root
• if a number has a factor then it must have a prime factor - therefore, generate all primes up to the square root and see if any of them divide evenly into the number being tested - these lists of prime numbers can then be saved and used again for future tests
• simple rules to knock out a large proportion of numbers which are not prime, e.g.
  • no prime number can end in 0, 2, 5, 4, 6, or 8 (as they must have 2 or 5 as a factor
  • if the digits in a number add up to a multiple of 3, than number is a multiple of 3 (i.e. 3 is a factor)
  • Fermat's method of attempting to express a number as the difference of two perfect squares because any such number cannot be prime (if X = A * A - B * B, it also equals (A + B) * (A - B), which means (A + B) and (A - B) are factors! He also had a method of simply checking to see whether a number can be easily expressed as the difference between two perfect squares.