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
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
=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
Newton Excel Bach, not (just) an Excel Blog 
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….
LikeLike
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?
LikeLike
Pingback: Excel Links of the Week - PHD’s new tag line [Nov 24] | Pointy Haired Dilbert - Chandoo.org
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..
LikeLike
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
LikeLike
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.
LikeLike
I hv simple formula in excell to find out prime number.
ur formula is also good.
LikeLike
i have some efficient way to find prime number in excell.
LikeLike
Hi Satish,
I am interested in your formula as well if you are willing to share 🙂
LikeLike
why not . I will send to all of u
LikeLike
Satish,
Would you mind posting the formula here (or sending it on)? I’ve been following this post too.
Thanks,
Eric
LikeLike
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.
LikeLike
please send me the formuals which were posted in the site
LikeLike
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
LikeLike
You can use roundup(sqrt(c8),0) instead of the int function and get rid of one OR condition.
LikeLike
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.
LikeLike
Pingback: Formula Forensics looks at Is my number a Prime Number? | Chandoo.org - Learn Microsoft Excel Online
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.
LikeLike
Thanks, that Tukhi thing looks interesting.
LikeLike
Pingback: Daily Download 26: Moving averages and prime numbers | Newton Excel Bach, not (just) an Excel Blog
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))))
LikeLike
The formula is incorrect.
It treats 9 as a prime number
LikeLike
Yes, there is no simple formula for prime numbers.
LikeLike
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 )
LikeLike
i think no one use to see………….
LikeLike
I can”t understant how i can write fortran program for determination of prime no………….can any body help me???????????????
LikeLike
Did you try a search?
There is some straightforward Fortran code here:
http://daviddeley.com/programming/code/factorf.htm
If you want something more refined, the last link in the post has different options using C, or I’m sure there are many open source routines available.
LikeLiked by 1 person
IsPrime function (SUM((N2/SEQUENCE(N2,1)=INT(N2/SEQUENCE(N2,1)))*1)=2)*1
Put that in a table with column titles “n” as the natural numbers 1, 2, 3, … and “isPrime” as the function above. Name the table primes. Now you can create a function for little omega (which is the count of distinct primes) as follows
=SUM(IF(SEQUENCE(primes[@n],1)*XLOOKUP(SEQUENCE(primes[@n],1),primes[n],primes[isPrime])=0,0,(INT(primes[@n]/XLOOKUP(SEQUENCE(primes[@n],1),primes[n],primes[n])*XLOOKUP(SEQUENCE(primes[@n],1),primes[n],primes[isPrime]))=primes[@n]/SEQUENCE(primes[@n],1)*XLOOKUP(SEQUENCE(primes[@n],1),primes[n],primes[isPrime]))*1))
Take the natural number 12. Then =XLOOKUP(SEQUENCE(primes[@n],1),primes[n],primes[isPrime]) gives an array of 12 1’s and 0’s for each number 1 to 12 with a 1 for prime and 0 otherwise.
Multiplying this by a sequence from 1 to 12 gives us an array of primes up to 12 or zero when the number is not prime.
We need to divide by this number when it is not zero which explains the IF statement, and then test to see if it is a whole number.
LikeLike