Finding Prime Numbers with Excel, and using Array Formulas

Download Primes.zip.

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

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

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

About these ads
This entry was posted in Arrays, Excel, Maths, Newton, UDFs, VBA and tagged , , , , . Bookmark the permalink.

25 Responses to Finding Prime Numbers with Excel, and using Array Formulas

  1. jonpeltier says:

    Actually,

    (MOD(C8,ROW(INDIRECT(”2:”&INT(SQRT(C8)))))0)

    returns an array of TRUE and FALSE values, while

    AND((MOD(C8,ROW(INDIRECT(”2:”&INT(SQRT(C8)))))0))

    returns TRUE if one or more values in this array is TRUE. Details….

  2. dougaj4 says:

    Jon – Thanks for the comment. I agree that what I said wasn’t quite right, but I don’t think that your statement is quite right either. I presume that WordPress ate your GT and LT symbols, so below I will refer to the two formulas as (MOD(…)) and AND(MOD(…)), which I hope will avoid confusion, rather than add to it.

    If I enter 25 in C8 then:
    (MOD (…)
    displays TRUE if entered without ctrl-shift.
    TRUE,TRUE,TRUE,FALSE if entered in a column with ctrl-shift-enter or
    {TRUE;TRUE;TRUE;FALSE} if evaluated with F2,F9

    AND(MOD(…))
    displays TRUE if entered without ctrl-shift.
    FALSE if entered with ctrl-shift-enter or
    {FALSE} if evaluated with F2,F9

    If I enter 26 in C8 then:
    (MOD (…)
    displays FALSE if entered without ctrl-shift.
    FALSE, TRUE,TRUE,TRUE if entered in a column with ctrl-shift-enter or
    {FALSE;TRUE;TRUE;TRUE} if evaluated with F2,F9

    AND(MOD(…))
    displays FALSE if entered without ctrl-shift.
    FALSE if entered with ctrl-shift-enter or
    {FALSE} if evaluated with F2,F9

    It was from that observation that I assumed that AND(MOD(…)) only looked at the first entry in the array if enterered without ctrl-shift; however if you enter MOD(…)) as a column array with ctrl-shift enter, say in cells C21:C24, then enter =AND(C21:C24), this correctly returns FALSE, no matter whether it is entered with ctrl-shift or not.

    So it looks to me like it is the (MOD(…)) function that needs to be entered as an array, otherwise it just returns one element (TRUE for 25 and FALSE for 26), and then the AND only looks at that one element.

    Does that sound right?

  3. Pingback: Excel Links of the Week - PHD’s new tag line [Nov 24] | Pointy Haired Dilbert - Chandoo.org

  4. Nadya Fermega says:

    Oh thanks for this good information. Hopefully the simple program using excel can inspired every body to get the highest prime numbers more than 13 million digits..

  5. Luis says:

    Excelent information about the undocumented features of MS Excel!!! But many questions remain:
    1. Why “2:5″ cannot be used as argument for INDEX(), but it is a valid argument when Index() is used as argument of Row()?
    2. Where are the array data stored?
    3. Under which circumstances double parenthesis are needed around the AND() arguments?
    Please provide references.
    Thank you,
    Luis

  6. dougaj4 says:

    Luis – The array formula is the work of Chip Pearson (see the top of the post for his address), I just broke it into pieces to see how it works, so I can’t be of much help with your questions, but:

    1: “Why “2:5″ cannot be used as argument for INDEX(), but it is a valid argument when Index() is used as argument of Row()?”

    I don’t know, that’s just the way it works.

    2: “Where are the array data stored?”

    I don’t know

    3. “Under which circumstances double parenthesis are needed around the AND() arguments?”

    I don’t think they are needed. It seems to work the same with single parentheses.

  7. satish kumar singh says:

    I hv simple formula in excell to find out prime number.
    ur formula is also good.

  8. satish kumar singh says:

    i have some efficient way to find prime number in excell.

  9. Sarah says:

    Hi Satish,

    I am interested in your formula as well if you are willing to share :)

  10. satish says:

    why not . I will send to all of u

    • Eric says:

      Satish,

      Would you mind posting the formula here (or sending it on)? I’ve been following this post too.

      Thanks,

      Eric

  11. sat.wnz says:

    I use to find out prime number with my new theory for prime number. Actually I have generated it so it is difficult to believe on way, how i use to find out. if u r interested i will sen u the formula and result.

  12. chandra shaker says:

    please send me the formuals which were posted in the site

  13. chandra shaker says:

    guys help me out in getting like : take a example as : 234 if i entered in cell and it should gives us : 432, 342,324, and all probabilites, please proivde the formula for that

  14. Yoel says:

    You can use roundup(sqrt(c8),0) instead of the int function and get rid of one OR condition.

  15. dougaj4 says:

    Yoel – Yes, using roundup(sqrt(c8),0) and deleting the initial IF(OR(C8=2,C8=3),”prime” works for 3. We still have to check for 2, so the formula becomes:

    =IF((C8=2),"prime",IF(AND((MOD(C8,ROW(INDIRECT("2:"&ROUNDUP(SQRT(C8),0)))).NE.0)),"prime","not prime"))

    where .NE. should be replaced with a less than sign followed by a greater than sign.

  16. Pingback: Formula Forensics looks at Is my number a Prime Number? | Chandoo.org - Learn Microsoft Excel Online

  17. kalx says:

    Late in the game, but http://tukhi.com has a demo for computing primes. After the install Tukhi/Demo/Primes sets you up with a spreadsheet using in-memory arrays that implement the sieve of Eratosthenes.

  18. Pingback: Daily Download 26: Moving averages and prime numbers | Newton Excel Bach, not (just) an Excel Blog

  19. Finding the prime numbers:
    =IF(A1=1,FALSE,IF(OR(A1=2,A1=3,A1=5)=TRUE,”TRUE”,NOT(OR((($A1/2)-INT($A1/2))=0,(($A1/3)-INT($A1/3))=0,(($A1/5)-INT($A1/5))=0))))

  20. rama says:

    The formula is incorrect.
    It treats 9 as a prime number

  21. satish kumar singh says:

    Every big prime twings gives smaller prime twings .
    Ex 11,13… ( 3,5 and 5,7 )
    Ex 17, 19……. (3,5 & 5,7 & 11,13 )
    Ex 29, 31……. (3,5 & 5,7 & 11,13 & 17,19 )
    Ex 41, 43……. (3,5 & 5,7 & 11,13 & 17,19 & 29,31 )

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s