Array formula to check if a number is prime [just for fun]

Posted on May 29th, 2009 in Learn Excel - 32 comments

I am math-geek-wannabe, if there ever is such a category. During my 3rd year of graduation I went and purchased the volume 2 of Donald Knuth‘s Art of Computer Programming and thus began my love with all things random and prime. I never really became the math-geek I always wanted to, instead I became an insurance expert with tons of passion for data and visualization. But when I get a chance to poke with randomness or numbers, I always lap it up with joy. And that brings us to an interesting array formula trick to check if a number is prime or not.

(assuming the number is in the cell B5) type the below formula and

=IF(MIN(MOD($B$5,ROW(INDIRECT("2:"&INT(SQRT($B$5))))))=0,"not prime","prime")

hit ctrl+shift+enter and bingo, it tells you if the number is prime or not.

how it works?

take a guess…

you are right. It just calculates the minimum of all reminders when the number x is divided by values between 2 and sqrt(x) and sees if it is zero. If so, the number is “not prime”, else, it is a “prime number”.

More random stuff on randomness and numbers

Shuffle a list of values in excel using random numbers

Bingo / Housie Tickets in Excel

Correct way to simulate dice throws in excel

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

32 Responses to “Array formula to check if a number is prime [just for fun]”

  1. Andy Holaday says:

    That is very cool! It doesn't handle inputs 2 or 3 correctly, but that can be forgiven.

    Using CEILING fixes the case of 3, but not 2:
    =IF(MIN(MOD($B5,ROW(INDIRECT("2:"&CEILING(SQRT($B5),1)))))=0,"not prime","prime")

    BTW I think you meant "assuming the number is in the cell B5"

    Incidentally, you and I have a lot in common... Love math, thought I was going to be a physics dude, ended up in the insurance industry with, as you say, tons of passion for data and visualization. Small world (^:

  2. Craig says:

    Hmmm.

    Try 9451 (=13X727) Says this is prime....

  3. Chandoo says:

    @Andy.. may be we write an if clause for 2 or 3 and that would be solved. But again we all they are prime.
    It is fun to know someone in the exact situation as me... ๐Ÿ™‚

    @Craig: Are you sure you have array entered the formula by pressing ctrl+shift+enter? Because, in my computer the same formula returns 9451 as not prime. I havent really checked the formula with all the prime numbers (and that is not possible too), but I have checked the logic and it should work.

  4. S Anand says:

    I tried 9451 -- works for me too. Nice one, Chandoo!

  5. Gerald Higgins says:

    9451 returns not prime for me too.

    I was curious to see if there was a limit to the size of the number that this would work with, and there is.
    For me, it works with 268,435,455, but for values 268,435,456 and upwards, it returns a #NUM error.
    Anyone know why it does this at this specific point ?

  6. Chandoo says:

    @Gerald... may be this is due to the limitation on (1) formula lengths or (2) array lengths. because 268,435,456's sqrt is 16384 which is 2^14. According to excel specifications here: http://office.microsoft.com/en-us/excel/HP051992911033.aspx and http://visio.mvps.org/Excel_2007.htm you can see that 16384 plays some special role in defining limits. Although I am not sure why MOD() would fail when it has 16384 arguments.. may be one of the mvps or excel devteam members can answer this...

    Also, checking primality is a very vast problem with so many heuristic and deterministic methods to solve it. The probablistic ones are your best bet if you aspire to calculate results fast, but they often fail.

    You can get a gist of methods from here http://en.wikipedia.org/wiki/Prime_number#Verifying_primality and http://primes.utm.edu/prove/

  7. Aires says:

    That's a great tip. Thanks, Chandoo! ๐Ÿ™‚

    I was also worried about numbers 2 and 3, but since these are the only special cases, it can be solved with:

    =IF(MIN(MOD($B5,ROW(INDIRECT(โ€2:โ€&INT(SQRT($B5),1)))))=0,IF(AND($B5=2;$B5=3),"prime","not prime"),"prime")

    (Please forgive for any misspell inside the above formula - I don't have Excel in English at work, and formula names change from one version to another. I also have no idea why, if you ask... ๐Ÿ™‚ )

  8. Gerald Higgins says:

    Chandoo - yes I thought it would be something like that.

    Aires - I think you'd want to replace the AND with OR in your formula.

  9. Aires says:

    Gerald - Yes, OR for sure. Thanks... ๐Ÿ™‚

    =IF(MIN(MOD($B5,ROW(INDIRECT(โ€2:โ€&INT(SQRT($B5),1)))))=0,IF(OR($B5=2,$B5=3),"prime","not prime"),"prime")

  10. Chandoo says:

    @Aires, sorry for the confusion, I have edited your formula since wordpress removed some symbols when you posted it. Unfortunately, i didnt change the AND to OR when I changed to AND conditions.. Thanks Gerald for pointing this out...

  11. Kalpesh says:

    Chandoo,

    I must say good resource for someone who wish to get better in excel. I am a dev. primarily in c# but I like VBA ๐Ÿ™‚

    What does 9427 return in your case? for me, it returns prime, while it is not.

    I tried it with this function & have to validate, if it works OK
    =IF(OR(MOD(A1,2) = 0, MOD(A1,3) = 0, MOD(A1,5) = 0, MOD(A1, 7) = 0) = FALSE, "prime", "not prime")

    You got me thinking & doing some fun stuff.
    Thanks.

  12. Kalpesh says:

    Chandoo,

    Can you tell me what does it return for 9427?
    My formula is incorrect in that case. ๐Ÿ™

  13. Chandoo says:

    @Kalpesh: 9427 works as well. It says not prime for me. I think there must be a mistake in the formula you have specified. As I said, checking for each and everyprime is not a good idea when you write such functions, instead you should check the logic and to me it seems perfect (well, within excel's limitations of handling arrays and large numbers)

    I am not sure why you would use a formula like (=IF(OR(MOD(A1,2) = 0, MOD(A1,3) = 0, MOD(A1,5) = 0, MOD(A1, 7) = 0) = FALSE, โ€œprimeโ€, โ€œnot primeโ€)), it would only work up to 7^2, that is 49.

    have you entered the formula =IF(MIN(MOD(a1,ROW(INDIRECT("2:"&INT(SQRT(a1))))))=0,"not prime","prime") as is and pressed ctrl+shift+enter in the cell ?

    Also, I am not sure if you have noticed, but array formulas work within spreadsheet. You need separate mechanism (preferably some loops) if you want to implement the same in VBA.

    To avoid some confusion, I am uploading the sample workbook where the formula is working here:

    http://chandoo.org/img/n/array-formula-to-check-prime.zip

    download and let me know if it still fails.

  14. Kalpesh says:

    I am sorry Chandoo.

    This is what happens when a developer does something in haste & wanting to check if it works & doesn't test it fully ๐Ÿ™‚

    That was me.

  15. Chandoo says:

    @Kalpesh... dont be sorry dear. Here at PHD, We are very proud of mistakes.

  16. Daniel Ferry says:

    @Chandoo-

    I've always used this array formula:

    =SUM((MOD(b5,ROW(INDIRECT("1:"&INT(b5^0.5))))=0)^1)=1

    or if I don't want an array formula:

    =SUMPRODUCT((MOD(b5,ROW(INDIRECT("1:"&INT(b5^0.5))))=0)^1)=1

    They return True or False. They count the number "1" as prime, which we all know it's not, so I just ignore that.

    I stumbled onto this post today, because I'm looking for an array formula to produce a list of all primes up to an arbitrary input number. Using formulas such as yours and mine, this is trivial on a worksheet with helper columns, but I'm looking for one formula that when array-entered over a range, as opposed to one cell, will produce these primes. For the life of me I don't know why MS has never included a function for this!

    Modifying my version of the primality test formula, I actually conjured a formula that would return the prime number if an indexed cell was prime and zero otherwise. But when I tried to enhance it further to eliminate all the zeros and condense the output array to nothing but the prime numbers (similar to removing blanks from a range), Excel would get confused and not produce the correct results.

    Have you ever heard of a way to do this?

    Regards,

    Daniel Ferry
    excelhero.com/blog

  17. Chandoo says:

    @Daniel... "Iโ€™m looking for one formula that when array-entered over a range, as opposed to one cell, will produce these primes. For the life of me I donโ€™t know why MS has never included a function for this!" hehe, me neither ๐Ÿ˜›

    I have studied primes and number theory during my undergrad (big big extra large Donald Knuth fan here :D). By definition prime numbers are unique and there is no function f(n) that will produce nth prime (well, there are some, but they work only up to certain value of 'n').

    So, it may be a good idea to write a UDF or VBA macro that would take 'n' as input and iterate from 1 until nth prime is found and then return the range.

  18. Daniel Ferry says:

    Chandoo:

    For the project I'm working on I'm trying to keep it VBA free.

    I know primes are unique, but any number within Excel's addressable range is easy enough to test for primality. I was simply trying to work out a way to do it recursively with an array formula. I got really close.

    But MS could have included this function for first few hundred thousand primes as a sort of built-in lookup table accessed from a function, like:

    =PRIME(n)

    A couple megabytes of Excel's sweeping size devoted to such a function would have made many scenarios much easier.

    Oh well...

    By the way, Chandoo, I'm working on a very interesting math-focused charting project that I hope to post to my blog in the next couple of days. Considering your background, I think you are going to like it!

    Daniel Ferry
    excelhero.com/blog

  19. Daniel Ferry says:

    Chandoo:

    Just wanted to let you know that I finished my project with the interesting math that I referred to in my last comment on this thread.

    It came out nice in my opinion and I'd love to hear your thoughts:

    http://www.excelhero.com/blog/2010/03/excel-a-presentation-platform.html

    By the way, I used my SUMPRODUCT version of the prime testing formula to generate the list of primes.

    Regards,

    Daniel Ferry
    excelhero.com/blog

  20. izabel says:

    Is a way to use MIN function and do not bring zero ?
    Exemplo in a list 3, 0, 5, 6 the min is 3 and never the zero.
    tks

  21. Daniel Ferry says:

    @izabel -

    If we put your numbers in the range A1:A4, you could use this formula to return the minimum non-zero, non-blank, and non-text value:

    =SMALL(A1:A4,COUNTIF(A1:A4,0)+1)

    .
    .
    .
    In practice, just extend the range as far down as you need.

    Regards,

    Daniel Ferry
    excelhero.com

  22. Kenneth says:

    I know this is a quite old post, but I'll give it a try. I'm trying to use this formula, but can't get it to work. Excel states that something is wrong with the formula and highlights the "ROW" part. Does it matter if I'm not using excel in English?
    Thanks.

  23. Hui... says:

    @Kenneth
    Some non English versions of Excel use ; instead of ,
    I'm not sure of other differences
    .
    You could try
    =IF(MIN(MOD($B$5;ROW(INDIRECT("2:"&INT(SQRT($B$5))))))=0;"not prime";"prime")
    You may also want to check =Row() by itself as well as the other key Functions, as your version may use different words?
    I can't help you out there
    .
    If this doesn't help let us know what language your using as one of the other great readers is bound to help you out

  24. Kenneth says:

    My excel is using the Swedish version. I tried your formula and got "NAME?", when I tried the formula in the original post it only highlighted the "ROW" part as mentioned. My first prime number is in B3 and goes down to B9.

    =IF(MIN(MOD($B$3;ROW(INDIRECT(โ€œ2:โ€&INT(SQRT($B$3))))))=0;โ€not primeโ€;โ€primeโ€)

    This is the formula I'm trying to use, but with zero success.

  25. [...] 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 [...]

  26. Michael Bryant says:

    I try to avoid that Shift-Ctrl-Enter stuff so thought I'd give this a go using sumproduct.ย 
    Limit is the number of rows Excel allows per sheet. Variable input is in cell A1.ย 
    =IF(AND($A$1<>1,(SUMPRODUCT((MOD($A$1,(ROW(INDIRECT("$A$1:"&"$A$"&$A$1))))=0)*1)<=2)),"Prime","Not prime")
    Regards
    MAB
    ย 

  27. Ockert says:

    Chandoo, your formula is very impressive and much more helpful than a piece of VBA functioning. It also works perfectly in Libreoffice CALC. Thanks for the trouble, and happy bracket counting.

  28. Rene Melek says:

    I tried the formula in Excel 2010 on several interesting numbers from the Bible. The number of verses in the New Testament is 7957, which is the product of two primes (109 x 73). The formula incorrectly reports that 7957 is prime. The number of chapters in the combined Old Testament and New Testament is 1189, again the product of two primes (41 x 23). The formula incorrectly reports that 1189 is prime. Something ain't right.

  29. Rene Melek says:

    Sorry, my bad. Forgot the Shift+Ctrl+Enter when entering the formula.

  30. Rajesh Janardhanan says:

    Hi I tried 540001 and it says it is Prime, but it is divisible by 7.
    540001/7=77143

Leave a Reply