Formula Forensics 024. Is this number a Prime Number ?

Posted on July 12th, 2012 in Formula Forensics , Huis , Posts by Hui - 16 comments

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.

 

 

 

Written by Hui...
Tags: , , , , , ,
Home: Chandoo.org Main Page
? Doubt: Ask an Excel Question

16 Responses to “Formula Forensics 024. Is this number a Prime Number ?”

  1. Jeff Weir says:

    Hui - great post. Couple of thoughts

    Your download spreadsheet is an .xls file, so is limited to 65k rows. THis means the largest number it can check is this:
    4,295,098,368
    ...which is the square of the number of rows in 'old' excel. 
    IF the file is resaved as an .xlsx then the largest NUMBER it can check is this:
    1,099,511,627,776
    ...and the largest PRIME it will find is this:
    1,099,513,724,917
    It fails on the next largest prime, which is this:
    1,099,513,724,941
    I've got a formula up my sleeve that I thought in theory would  check numbers up to this:
    72,057,594,037,927,900
    ...although Excel gives up if I exceed this:
    44,929,149,915,683
    ...and I've actually managed to successfully check this prime:
    44,929,149,915,581
    ...which I'm pretty happy with. Expecting the FBI to knock on my door pretty soon 🙂
    There's a handly prime number checker and generator at http://www.numberempire.com/primenumbers.php

    • Jeff Weir says:

      Interesting: I can get my formula to correctly return primes up to 199,999,999,999,903. But past 200,000,000,000,000 it fails. I wonder if 200,000,000,000,000 is significant somehow in regards to Excel's calculation engine?

      • Jeff Weir says:

        Whoops, I meant the largest prime I've been able to find is 199,999,999,999,997 but it fails past 200,000,000,000,000

    • Hui says:

      @Geoff
      Thanx for the comments 
      I wrote this last week and saved the sample file as an *.xls file to be compatible with all readers and then forgot to make the qualification about the Row limit in Excel 97/03 and impact on the Primality Test in previous versions of Excel.
      There are several techniques for testing primality of which this method (the Brute Force approach) is easiest to implement and explain.
       

  2. Jeff Weir says:

    Good discussion of whether 1 is a prime at http://en.wikipedia.org/wiki/Prime_number
    You might need to amend your formula to discount 1 in order to please the purists!
     
     

  3. David Hager says:

    This array formula returns TRUE if the number in cell A1 is a prime number.

    =OR(A1=2,A1=3,ISNA(MATCH(TRUE,A1/ROW(INDIRECT("2:"&INT(SQRT(A1))))=
    INT(A1/ROW(INDIRECT("2:"&INT(SQRT(A1))))),0)))

  4. daffy333 says:

    {=SUM(--(MOD(A1,ROW($A$1:INDEX($A:$A,A1)))=0))<3}
    This formula includes 1 as a prime number.
    Cheers!

  5. Ola says:

    Good to see.
    I was just asking at 'Daily Dose of Excel' if this formula was valid:
    =SUMPRODUCT(--(MOD(A2;ROW(INDIRECT("2:"&A2)))=0))=1
    And now I found the above formula which seams to confirm it is.
    Also interesting that virtually the same formula pops up just 1 day apart.
    //Ola

    ...the formula works for all numbers from 1 to infinity...in princip, since Excel can't address rows below 1.048.576.
    As a speed test; to calculate one number of 1.000.000 is no problem but to check all 1.000 numbers between 100.000 -101.000 is a bit slow.

    • Jeff Weir says:

      @Ola: it's worth noting that - paraphrasing Hui's post above - a number can't be a prime number if any integers between 2 and the square root of the number will divide into it.
      This means that you don't have to test every number up to the number itself, as you do with ROW(INDIRECT(“2:”&A2))
      Instead, you can use ROW(INDIRECT(“2:”&SQRT(A2)))
      Which also means that you are no longer limited to checking numbers up to Excel's row limit of 1,048,576 but instead can now check them up to the square of excel's row limit: 1,099,513,724,917
      And if you're really crafty,  you can check numbers well beyond this too (although not with any of the formulas posted above). As per my comment above, I've got a formula that correctly returns primes up to 199,999,999,999,903. But past 200,000,000,000,000 it fails. I'm in the process of writing up a blog post on this, and will share it when I'm done.
       

  6. jomili says:

    Hui,

    I think you have an error in your instructions.  The instructions say to put this formula in F8:
    =SUMPRODUCT(1*MOD(B2, ROW(OFFSET($A$1,,, Int(Sqrt(B2)),1)) )=0)
    The formula in your example file in F8 is this:
    =SUMPRODUCT(1*(MOD(B2,ROW(OFFSET(A1,,,INT(SQRT(B2)),1)))=0))

    • Hui... says:

      @Jomili

      I think I may fire my proof reader!

      The $ signs aren't important in this instance, provided the formula isn't dragged somewhere else. The Formula must refer to a cell in Row 1 instead of A1 wherever it is located.

      The spacing is added so that that I have some control over the word wrapping that wordpress uses, where if i remove the spacing in the formula i get word wrapping that isn't in good locations.

       

       

       

  7. JIALIN says:

    =AND(MOD(L19,ROW(INDIRECT("2:"&INT(SQRT(L19))))))

  8. Jeff Weir says:

    @Jialin: that use of AND is sheer genius. It completely does away with the need to use SUM or SUMPRODUCT. Just awesome!

  9. Michael says:

    Hi Hui - A bit off-topic, but you may be interested in this entry for the global TED Conference by Adam Spencer about his passion for prime numbers. He's a mathematician, and also a broadcaster on ABC Radio.
    http://talentsearch.ted.com/video/Adam-Spencer-A-lifelong-passion;TEDSydney

  10. Peter Mown says:

    Here is a great online prime number checker which can check numbers up to 5000 digits http://numberworld.info/primeCheck

Leave a Reply