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
33 Responses to “Array formula to check if a number is prime [just for fun]”
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 (^:
This fails for non prime numbers like 10403, 1763 etc
Hmmm.
Try 9451 (=13X727) Says this is prime....
@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.
I tried 9451 -- works for me too. Nice one, Chandoo!
@Anand.. you are welcome 🙂
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 ?
@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/
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... 🙂 )
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.
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")
@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...
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.
Chandoo,
Can you tell me what does it return for 9427?
My formula is incorrect in that case. 🙁
@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.
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.
@Kalpesh... dont be sorry dear. Here at PHD, We are very proud of mistakes.
@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
@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.
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
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
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
@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
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.
@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
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.
[...] 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 [...]
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
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.
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.
Sorry, my bad. Forgot the Shift+Ctrl+Enter when entering the formula.
Hi I tried 540001 and it says it is Prime, but it is divisible by 7.
540001/7=77143
sir,
i needed an excel formula for identifying prime numbers, i found it on your website, and its working 🙂
kindly accept my gratitude for the same,
wishing you flying colours for future endeavors ...