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