How do I test for a prime number?

[Guest]

Aside from a lookup table of primes, is there any neater way of detecting
that a number is prime?

 

[Bob Phillips]

Here is a routine originally presented by Myrna Larson that I use to test
for primes.


=IsPrime(num)


returns True or False


Function IsPrime(TestNum As Long)
Dim PrimeCnt As Long
Dim y As Long
Dim x As Long
Dim i As Long
Dim Flag As Boolean
Dim Primes() As Long
Dim NumStop As Double
ReDim Primes(1 To 2)

NumStop = Sqr(TestNum)
If TestNum = 1 Or TestNum = 2 Or TestNum = 3 Or TestNum = 5 Then
IsPrime = True
Exit Function
End If
Primes(1) = 2
Primes(2) = 3
PrimeCnt = 2
x = 3

Do
x = x + 2
For y = 3 To Sqr(x) Step 2
If x Mod y = 0 Then GoTo NoPrime1
Next y
PrimeCnt = PrimeCnt + 1
ReDim Preserve Primes(1 To PrimeCnt)
Primes(PrimeCnt) = x
NoPrime1:
Loop Until Primes(PrimeCnt) > NumStop

For i = LBound(Primes) To UBound(Primes)
If TestNum Mod Primes(i) = 0 Then
IsPrime = False
Exit Function
End If
Next
IsPrime = True
End Function

 

[Rich_z]

Have a look at
http://www.dicks-blog.com/archives/2005/06/30/is-this-number-prime/

 

[Harlan Grove]

Bob Phillips wrote...

Here is a routine originally presented by Myrna Larson that I use to test
for primes.

=IsPrime(num)

....

Picky: 1 isn't a prime number any more. See

http://mathworld.wolfram.com/PrimeNumber.html

Next a udf implementing the sieve of Eratosthenes is nice but slow.
Since your udf only handles long integers, the largest possible factor
is

INT(SQRT(2^31-1))

or 46340, which is comfortably less than Excel's max row count (at
least for XL97 and subsequent). So a simple worksheet formula would
suffice.

=SUMPRODUCT(--(MOD(N,ROW(INDIRECT("2:"&INT(SQRT(N)))))=0))=0

That's inefficient. It can be speeded up at the cost of complexity.

=OR(N={2;3;5;7},IF(AND(N>10,MOD(N,2)=1),
SUMPRODUCT(--(MOD(N,1+2*ROW(INDIRECT("1:"&INT(SQRT(N)/2))))=0))=0))

If the OP or anyone else needs to check larger numbers, there are much
better tools to use than Excel or VBA.