Several of the puzzles at Project Euler (see previous post) require the finding of prime numbers, for instance what is the 10,001th prime number? Searching the Web for some ready made solutions I found this array formula at Chip Pearson’s site:
=IF(OR(C8=2,C8=3),”prime”,IF(AND((MOD(C8,ROW(INDIRECT(“2:”&INT(SQRT(C8)))))<>0)),”prime”,”not prime”)) *
* This formula is slightly amended from the one on Chip’s site, which treated 1 as a prime, and divided by all numbers up to C8-1, rather than SQRT(C8)
Quoting from Chip’s site:
“This is an array formula, so you must press CTRL SHIFT ENTER rather than just ENTER when you first enter the formula and whenever you edit it later. If you do this properly, Excel will display the formula enclosed in curly braces { }. See the array formulas pagefor much more detail about array formulas. Note that the formula will not work properly if you do not enter it with CTRL SHIFT ENTER. This formula will work with numbers up to 268,435,455, after which Excel’s ability to handle the intermediate array fails. “
Now it may not be immediately obvious to you how that formula works, certainly it was not at all obvious to me,so let’s break it down into small chunks:
Breakdown of an array formula
Entering 25 in cell C8:
=”2:”&INT(SQRT(C8)) returns 2:5
=ROW(INDIRECT(“2:”&INT(SQRT(C8)))) returns a column array with the numbers {2;3;4,5}
=MOD(C8,ROW(INDIRECT(“2:”&INT(SQRT(C8))))) returns a column array with the remainder of 25 divided by the members of the array above {1;1;1,0}
=AND((MOD(C8,ROW(INDIRECT(“2:”&INT(SQRT(C8)))))<>0)) returns TRUE if all the remainders are greater than zero, or FALSE if there are one or more zeroes, and finally
=IF(AND((MOD(C8,ROW(INDIRECT(“2:”&INT(SQRT(C8)))))<>0)),”prime”,”not prime”) returns “prime” if the statement above is TRUE, or “not prime” if it is FALSE.
The initial: =IF(OR(C8=2,C8=3),”prime”,… is required because the main formula does not work for values less than 4, so it is necessary to check for entered values of 2 or 3 (but not 1, which is not defined as a prime number).
The reason why this formula must be entered as an array formula is that it is necessary to check for all the divisions in the array generated by the ROW statement. If the formula is enetered without pressing “Ctrl-Shift-Enter” the AND function only checks the first member of the array, and finds that all odd numbers are prime numbers.
This is an excellent example of the power of an array formula, allowing complex multi-stage computations to be carried out in a single cell; it is however not of much use for Project Euler purposes, which required finding the 10,001st prime for instance. For that purpose I have written my own prime UDF – download here.
A UDF to generate a sequence of primes
=Prime(MaxVal, First, Last)
This function will find all the prime numbers in a given range (e.g. from the 99,995th to 100,001st prime as shown above). If “First” is not entered or is zero the function checks if MaxVal is prime.
For checking if one number is prime the UDF uses a similar approach to the array function, except that it only checks odd numbers, since we know that even numbers other than 2 cannot be prime.
For generating a range of primes it uses the “Sieve of Eratosthenes” method:
- Set up an array from 1 to MaxVal
- Enter a 1 for each number in the array divisible by 2 or 3
- For each odd number from 5 to MaxVal:
- If its array value = 1, it is not prime, check the next odd number
- If its array value = 0, it is prime, add it to the prime list and enter 1 for each number in the array that is an odd multiple of this prime number.
- Stop when the last prime in the required sequence has been found, or MaxVal has been reached.
More refinements on the Sieve of Eratosthenes method are given here: Fun With Prime Numbers
Newton Excel Bach, not (just) an Excel Blog 