Is this number prime?
In one of my (many) previous lives, I wanted to be a mathematician.
Even after I realized that being a mathematician would preclude a lifestyle that I wanted to become accustomed to, I still retained an active interest in mathematics. One of the areas that I found fascinating involved prime numbers.
I’ve seen many UDFs in the newsgroups, mostly provided by Excel MVPs, to determine if a number is prime. However, the following is the shortest UDF that I’ve been able to come up with:
Dim i As Long
If Num < 2 Or (Num <> 2 And Num Mod 2 = 0) _
Or Num <> Int(Num) Then Exit Function
For i = 3 To Sqr(Num) Step 2
If Num Mod i = 0 Then Exit Function
Next
IsPrime = True
End Function
The reason for declaring the input number Num as a Single is that if it’s declared as an Integer or a Long, an input value of, say, 3.2 will be coerced to 3 and be evaluated as a prime number. Clearly, this is not the desired result. There is probably a better way of handling this, but I can’t figure it out.
I’d be interested in some comments as to whether this code can be shortened or made more elegant.
Couple of quick notes:
- break up the compound conditional statements; VBA doesn’t short-circuit, so you’ll be doing more work than necessary unless you give each condition its own IF
- use Fix instead of Int to avoid the overhead of unnecessary (bankers) rounding
- before embarking on a whole lot of MODs, consider adding the digits in the number together and MOD’ng with 3
- another quick saver is to store an array of known primes (up to 200, let’s say) and divide your prospective prime by them before embarking on a loop
Oops, forget the Int/Fix comment — my 3AM brain was thinking CInt.
I wonder how large a number you can use without clogging up your cpu resources. A long time ago, I used to run a program to check for mersenne prime numbers (2^prime number - 1) and it used to take weeks to determine the answer. For more interesting info on Mersenne prime numbers you can check out this site - http://www.utm.edu/research/primes/mersenne/
In case you’re wondering I sometimes still want to be a mathematician. It fascinates me.
This seems to work for primes > 3.
If Num Int(Num) Then Exit Function
Select Case Num Mod 6
Case 1, 5
Dim i As Long
For i = 5 To Sqr(Num) Step 6
If Num Mod i = 0 Then Exit Function
If Num Mod i + 2 = 0 Then Exit Function
Next i
Case Else
Exit Function
End Select
IsPrime = True
I dont understand why you wouldnt just put on a graph of prime #s
u absoulutley need to do this! plz and thanx
Devyn Fortunati
It’s faster just to divide by known primes up to Sqr(Num) as Eric Bachtal says. No need to divide by all odd number or all numbers that are congruent to 1 mod 6 and 5 mod 6. Faster still if you are trying to find all prime numbers in a certain range (so I’ve heard — I plan to test this out myself when I have a chance) is to set up a Sieve of Erastothenes, which eliminates numbers that aren’t prime, rather than testing every number for primeness.
the fastest way to find consecutive primes is to create an array and cross out all the non prim numbes.
any way here is a very basic prime checker
http://logic-dust.blogspot.com/2006/08/primary-number-checker.html
If you are interested in a worksheet formula to determine if a number is prime (no VBA required), you can use the following array formula. It will test numbers between 2 and 65536 (Excel 2003 and earlier) or between 2 and 1,000,000 (Excel 2007). It tests whether the number in A1 is a prime, a prime twin, or not prime.
=IF(AND((MOD($A$1,ROW(INDIRECT(”2:”&$A$1-1)))0)),IF(OR(AND((MOD($A$1-2,ROW(INDIRECT(”2:”&$A$1-3)))0)),AND((MOD($A$1+2,ROW(INDIRECT(”2:”&$A$1+1)))0))),”prime twin”,”prime”),”not prime”)
Since this a an array formula, you MUST press CTRL SHIFT ENTER rathen than just Enter when you enter the formula and whenever you edit later. I have no idea if there is really a practical use for this, but it is kind of cool.
Chip’s approach is very inefficient and unreliable.
First, 2 is the only even prime number. No prime number can have an even even factor less than itself. Second, if a number is nonprime, it’ll have a factor > 1 and 2^29. Very unwise to use Excel’s MOD in any formula involving factorization of arbitrary numbers.
So longer but more efficient to use
=IF(OR(A1INT(A1),A12,A1/2=INT(A1/2))),”not prime”,
IF(OR(A1/(2*ROW($A$1:INDEX($A:$A,INT(SQRT(A1)/2)))+1)
=INT(A1/(2*ROW($A$1:INDEX($A:$A,INT(SQRT(A1)/2)))+1))),
“not prime”,”prime”))
fzz’s array formula results in an error, and without trying to understand it fully I’ve come up with the following corrected version, which seems to work:-
=IF(OR(A1INT(A1),A12,A1/2=INT(A1/2)),”not prime”,IF(OR(A1/(2*ROW($A$1:INDEX($A:$A,INT(SQRT(A1)/2)))+1)=INT(A1/(2*ROW($A$1:INDEX($A:$A,INT(SQRT(A1)/2)))+1))),”not prime”,”prime”))
I found this old post on John Walkenbach’s site http://j-walk.com/ss/excel/eee/eee015.txt (I have no idea at all about the formula’s efficiency or reliability, other than to say that it worked quickly and accurately on the 50 or so tests I gave it):-
by Bob Umlas
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)))
Use it as a conditional formatting formula, with A1 as the active cell in the selection to be formatted.
Here’s how Bob’s amazing formula works. In a nutshell, the number is divided by all potential prime factors, and the resulting array is tested to see whether it contains a whole number. If is does, you have a prime
number. A limitation of this formula is that it cannot test numbers that are greater than 65535^2. This is due to the array size constraint in Excel 97/2000.
That’s odd - the “” that I included after the first “A1″ didn’t print in my post (maybe that happened to fzz too). The other error (one too many right brackets after the second “A1/2″) printed ok. Let’s see what happens now…
I would have liked to edit my first post, but can’t see how.
Btw, I just found and installed the freeware “Morefunc” collection of additional Excel worksheet functions. It includes “PN.ISPRIME”, which tests for primality. Works well, from what I’ve seen.
The following array formula will test if a number is prime.
=IF(A1=2,”Prime”,IF(AND((MOD(A1,ROW(INDIRECT(”2:”&ROUNDUP(SQRT(A1),0))))0))=TRUE,”Prime”,”Not Prime”))
You must press Ctrl Shift and Enter after you enter it.
The formula relies on Excel’s MOD function to calculate the remainder on every whole number divisor from 2 to
the square root of the test number. If there is always a remainder then the number is prime.
Excel’s ability to calculate the remainder fails when the test number exceeds 268,435,455.
You can download my workbook here:
http://www.excelexchange.com/prime_number_test.html