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:

Function IsPrime(Num As Single) As Boolean
    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.

Posted in Uncategorized

20 thoughts on “Is this number prime?

  1. 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

  2. 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.

  3. 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

  4. 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

  5. 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.

  6. 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.

  7. 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”))

  8. 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.

  9. 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.

  10. 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

  11. Just curious, is this a valid test for a prime number?
    =SUMPRODUCT(–(MOD(A2;ROW(INDIRECT(“2:”&A2)))=0))=1
    ..excluding number 1
    //Ola Sandström

  12. @fzz…would you be able to explain your comment “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.”

    Specifically, A) I’m lost on the significance of 2^29 and B) I don’t understand why the use of MOD is unwise.

    Also, looks like the parser ate some of your formula…specifically this bit:
    OR(A1INT(A1),A12,
    I imagine you put something like OR(A1 NOT EQUAL TO INT(A1), A1 NOT EQUAL TO 2, …

  13. Interesting…I’ve got a very tricky worksheet formula that correctly return primes up to 199,999,999,999,903. But past 200,000,000,000,000 it fails. I wonder if 200,000,000,000,000 is significant somehow in regards to Excel’s calculation engine?

  14. @fzz…in relation to my previous question I see that the MOD function has a bug, discussed at http://excel.tips.net/T003302_Large_Numbers_in_the_MOD_Function.html THat site says the MOD function returns an error if the divisor (the second argument in the MOD function), multiplied by 134,217,728, is less than or equal to the number being evaluated (the first argument in the MOD function).

    Interestingly that site says the bug has been fixed in Excel 2010, but it looks like it still fails, but at bigger numbers. MOD(2251799999999,2) works, but anything larger fails.

  15. Hi Dick,

    I too have a love for maths and still love finding bigger and bigger prime numbers. I have also looked into Mersenne prime numbers and set about writing a procedure.

    It quickly became apparent that I would need to read the known prime numbers in from a text file up to the sqrt(n) using the trial division method. Once the array of known prime numbers was created I then set about testing each number with the known prime numbers. I have also used MOD in my formula which has allowed me to test up to 200,000,000. My procedure also write its results to a waiting text file (which can be over 60MB in size when it is finished) and tells me the number of primes found and how long the program took to run.

    Code as follows:

    Application.ScreenUpdating = False

    ‘ Initialize variables.
    Counter = 0

    Open “H:\Prime Numbers.txt” For Input As #1
    Open “H:\Results.txt” For Output As #2

    lower = InputBox(“Please enter the lower limit.”, “Lower Limit”)
    upper = InputBox(“Please enter the upper limit.”, “Upper Limit”)

    Do While Not EOF(1)
    Line Input #1, InputData ‘ Read line of data.
    If Sqr(upper) > CDbl(InputData) Then
    a = a + 1
    ReDim Preserve TextFile(1 To a)
    TextFile(a) = CDbl(InputData)
    Else
    Exit Do
    End If
    Loop
    Close #1 ‘ Close file.

    Start = Timer

    For x = lower To upper
    For b = 1 To a
    prime_number = True
    If x Mod TextFile(b) 0 Or x = TextFile(b) Then
    ‘do nothing
    Else
    prime_number = False
    Exit For
    End If
    Next b
    If prime_number = True Then
    ‘ Update the percentage completed.
    PctDone = (x – lower) / (upper – lower)
    ‘ Call subroutine that updates the progress bar.
    UpdateProgressBar PctDone
    Print #2, x
    Counter = Counter + 1
    b = 1
    End If
    Next x

    Print #2, “Number of prime numbers: ” & Counter
    Close #2

    Finish = Timer
    totaltime = Format(Finish – Start, ttttt)
    hours = totaltime \ 3600
    minutes = (totaltime \ 60) – (hours * 60)
    seconds = totaltime Mod 60

    complete = MsgBox(“Completed in ” & hours & “h ” & minutes & “m ” & seconds & “s.”, vbOKOnly, “Calculations complete”)

    It may not be elegant and there may be better ways to do it, but this way certainly works for me.

    Cheers for the post and keep up the good work!

    Regards,

    Ken


Posting code? Use <pre> tags for VBA and <code> tags for inline.

Leave a Reply

Your email address will not be published.