Since Formula Forensics commenced I have received a number of requests for a formula to check if a number is a Prime Number. Although a test for Prime Numbers has been posted before at Chandoo.org, Refer here, this is a good chance to build up an array formula from scratch using the Primality Test as an example.
So today in Formula Forensics we will examine Prime Numbers and a formula to determine if a given number is how this works and then how it can be extended to Sum the values in another field as well.
As always at Formula Forensics you can follow along using a Worked Example which you can download here: Excel 97-2010 Sample File.
Whats a Prime Numbers
Prime Numbers occur in nature in an amazing number of situations from Plant Growth to the occurrence of Cicadas in a Forrest. Prime Numbers are extensively used in mathematics and form the basis of modern Cryptography.Before we jump into the formula it is worth explaining a little bit about Prime Numbers and there properties as this will aid us in developing a formula to check if a number is Prime, its Primality.
The definition of a Prime Number is an integer number greater than 1, which is only evenly divisible by two integers, being one and itself.
Lets look at two numbers.
16 – Sixteen isn’t a prime number as it is evenly divisible by the numbers 1, 2, 4, 8 and 16.17 – Seventeen is a prime number as it is only evenly divisible by the numbers 1 and 17.
We can see that we need to check all the integers from 1 through to the square root of the number.
Integers greater than the square root cannot divide into the original number evenly by default.
We can now also now see that if a number is a prime number then only one Integer between 1 and the square root of the number will divide into the number, that number is one.
Lets look at our two numbers again.
16 (non Prime) – Square Root is 4, But integers 1, 2, & 4 can divide into 16 evenly
17 (Prime) – Square Root is 4, But only the integer 1 can divide into 17 evenly
So we can use that property to check if a number is a prime.
That is the count of the integers which can be evenly divided into the number between 1 and the Integer of the Square Root of the number will be 1 if the number is a prime.
So we will test each Integer between 1 and the Square root of the number.
If any of those integers (except for the number 1) divide into the test number evenly with no remainder, then we know the test number is not a prime number.
If the count of numbers that divide into the number is 1 then the number is a prime.
How to Develop a Prime Number Test Formula
We have used a method in Formula Forensics several times for setting up an array of integers and that is Row(Offset($A$1,,,n,1))This establishes an array of the numbers 1 .. n
We established above that n is the square root of the Prime Candidate. In fact it is the integer of the square root of the Prime Candidate.
That is the largest Integer which is less than the Square Root of the Prime Candidate.
If our prime candidate is 16, n = Square root (16) = 4
If our prime candidate is 17, n = Integer(Square root (17)) = 4
If cell B2 contains our Prime Candidate, lets use 100
In a Blank cell E2, enter =Row(Offset($A$1,,,Int(Sqrt(B2)),1)) where n = int(Sqrt(B2)); Don’t press Enter press F9
Excel will display: ={1;2;3;4;5;6;7;8;9;10}
We next need to check if each of these numbers is evenly divisible into our Prime Candidate.
Excel has a function Mod() that will assist us.
Mod() has the syntax:
Mod returns 0 when a number can divide into another number evenly
So we can use the formula:
=MOD(B2, ROW(OFFSET($A$1,,, Int(Sqrt(B2)),1)) )
Where B2 is the number we are checking for Primality
If We make B2 =100 and in a Blank cell F4 enter:
=MOD(B2, ROW(OFFSET($A$1,,, Int(Sqrt(B2)),1)) ) Don’t press Enter press F9
Excel responds with ={0;0;1;0;0;4;2;4;1;0}
We can see that Mod(100, 1) = 0, Mod(100, 2) = 0, Mod(100, 3) = 1 etc
If the value is 0 in the above Table or Array it is evenly divisible into the Prime Candidate
We can convert these into a True/False using a quick = 0 addition to the formula
If we make B2 =100 and in a Blank cell F6 enter:
=MOD(B2, ROW(OFFSET($A$1,,, Int(Sqrt(B2)),1)) )=0 Don’t press Enter press F9
Excel responds with ={TRUE;TRUE;FALSE;TRUE;TRUE;FALSE;FALSE;FALSE;FALSE;TRUE}
We will use Sumproduct to count the number of True values by converting them to 1 using:
1*MOD(B2, ROW(OFFSET($A$1,,, Int(Sqrt(B2)),1)) )=0
and we will use Sumproduct to add up the individual array elements
=SUMPRODUCT(1*MOD(B2, ROW(OFFSET($A$1,,, Int(Sqrt(B2)),1)) )=0)
The 1* forces each element of the Array to be evaluated as 1 * True/False resulting in an array of 1/0’s.
In a blank cell F8, enter =SUMPRODUCT(1*MOD(B2, ROW(OFFSET($A$1,,, Int(Sqrt(B2)),1)) )=0)
Excel will respond with 5
This tells us there are 5 numbers between 1 and 10, the Sqrt(100), which are even divisible into 100
We saw this above with
“Excel responds with ={0;0;1;0;0;4;2;4;1;0}”
These 5 integers are 1, 2, 4, 5, 10
Finally to check if the number is a Prime this answer should be 1
This gives us our final formula of:
=SUMPRODUCT(1*(MOD(B2,ROW(OFFSET(A1,,,INT(SQRT(B2)),1)))=0))=1
Refer to cell F10 or C2
You can try out any number in cell b2 and see if it evaluates as a Prime Number
More Prime Number Formulas
You can look at other Prime Number solutions using Formulas and VBA at the following links:Chandoo.org
Daily Dose of Excel
Newton Excel Bach
Microsoft
Download
You can download a copy of the above file and follow along, Download Here.Formula Forensics “The Series”
This is the 24th post in the Formula Forensics series.You can learn more about how to pull Excel Formulas apart in the following catalog Formula Forensic Series
Formula Forensics Needs Your Help
I need more ideas for future Formula Forensics posts and so I need your help.If you have a neat formula that you would like to share and explain, try putting pen to paper and draft up a Post like above or;
If you have a formula that you would like explained, but don’t want to write a post, send it to Hui or Chandoo.
0 comments:
Post a Comment