# Prime numbers

## Add-in that factorises relatively small numbers

This add-in contains three worksheet functions.

Prime factorises a number in a single worksheet cell. If it can't find a factor, it states that the number is a prime. The function works by trial division. I have included a ceiling in the function after which it stops. You can increase the ceiling but the function will be slower.

NextPrime finds the next prime bigger than a given number.

FermatPseudo applies the Fermat test to find pseudoprimes.

The Fermat test is used to find out whether large numbers are prime.

 If base ^ (p – 1) mod p = 1 then p is probably a prime

The test finds all prime numbers but also picks up a few others, which are actually composite. These are called "pseudoprimes".

For small numbers, trial division is a much easier way to find prime numbers. For this reason I decided to eliminate actual primes first and use the FermatPseudo function to find just pseudoprimes.

Excel is not well suited to factorise big numbers. See beyond Excel.

If you want a simple table with the prime numbers highlighted, have a look at primes with xsl under my non-Excel pages.

Interesting things to do
Find the smallest pseudoprimes in base 10. Look for numbers that are pseudoprimes in several bases.

Prime.zip contains two files

 a) prime.xla – the add-in described above b) prime examples.xls – gives a few examples of the functions in the add-in. Download prime.zip (24kb) The prime pages is an excellent site with a very good selection of links. You might also like prime puzzles particularly number 12, which involves decimal repeat cycles. home