Is there a formula for identifying prime numbers in Excel?

[t_elam]

I have some mathematic formulas that I am working with, and I need to see
what formulas generate prime numbers. Please let me tell me if you know a
way of getting Excel to identify which numbers are prime.

Thanks,

 

[Joel]

How large are your numbers? sometimes it is more effficient to make a table
of prime numbers and perform a lookup to determine which numbers are prime
and which numbers are not prime.

 

[Gary''s Student]

http://support.microsoft.com/?kbid=202782

 

[cht13er]

How large are your numbers?  sometimes it is more effficient to make a table
of prime numbers and perform a lookup to determine which numbers are prime
and which numbers are not prime.






- Show quoted text -

You can get the first 5,000 prime numbers pretty quickly (I did it the
other day) by looking only at odd numbers and checking each new number
(say 5) against every number above it (3) .. so if 5Mod3 = 0 then it's
not a prime number ...

HTH

Chris

 

[Mike H]

a function perhaps

Function isprime(rng As Range) As Boolean
'calculate primes
Dim i As Long
If IsNumeric(rng.Value) Then
For x = 2 To 1000000000
If (x <> 2 And x Mod 2 = 0) Or x <> Int(x) Then GoTo 100

For i = 3 To Sqr(x) Step 2
If x Mod i = 0 Then GoTo 100
Next
If x = rng.Value Then isprime = True: Exit Function
If x > rng.Value Then isprime = False: Exit Function
100
Next
End If
isprime (rng)
End Function

Mike

 

[Peter T]

Another one -

Function Prime(num As Long) As Boolean
If num Mod 2 Then
Prime = True
For i = 3 To num \ 3 Step 2
If num Mod i = 0 Then
Prime = False
Exit For
End If
Next
End If
End Function

Sub test()
Dim i As Long
Dim rw As Long
For i = 1 To 10000 Step 2
If Prime(i) Then
rw = rw + 1
Cells(rw, 1) = i
End If
Next
End Sub

Perhaps ought to allow 2 to pass as a prime number, which as written it
doesn't for sake of speed.

Regards,
Peter T

 

[Peter T]

This might be more efficient with larger numbers, no need to check Mod
beyond the sqr root of the number, at least I assume not ?

Function Prime(num As Long) As Boolean
If num Mod 2 Then
Prime = True
For i = 3 To Int(Sqr(num)) Step 2
If num Mod i = 0 Then
Prime = False
Exit For
End If
Next
End If
End Function

Not thoroughly tested !

Regards,
Peter T

 

[Mike H]

Peter,

I would suggest you trap for 1 which your function evaluates as a prime
number and 2 which your function evaluates as a non prime.

Mike

 

[Peter T]

I did mention previously the function (as written)) did not return 2 as a
Prime but you're right to point out that it incorrectly returned 1 as a
Prime.

Function Prime(num As Long) As Boolean
If num < 4 Then
Prime = num > 1
ElseIf num Mod 2 Then
Prime = True
For i = 3 To Int(Sqr(num)) Step 2
If num Mod i = 0 Then
Prime = False
Exit For
End If
Next
End If
End Function

Please feel free to validate this, or otherwise, and/or suggest any ways to
make it more efficient with large numbers.

If anyone wants a list of Primes just add these two lines above the
For..loop in the Test routine I posted earlier
rw = 1
Cells(rw, 1) = 2
For i = 3 To 10000 Step 2

Regards,
Peter T

 

[Dana DeLouis]

This might be more efficient

For i = 3 To Int(Sqr(num)) Step 2

Just be aware that 20% of the time your 'i' value ends in 5.
Numbers that end in 5, ie 25, 35,45, etc are also divisible by 5.
Hence, checking 5's is a waste. However, the time involved getting around
this is probably not worth it.

It's too bad Microsoft refuses to fix the MOD bug with Excel, even in xl
2007.
One is still limited in vba to the number 2147483647 !!
Sure wish Microsoft would fix this. It would make a lot of code easier to
write.

Sub Demo()
On Error Resume Next

Debug.Print 2147483647# Mod 2 'Ok
Debug.Print 2147483648# Mod 2 '(Error Limit!)

'// Can't do this of course
Debug.Print 268435455999# Mod 2000

'// Worksheet MOD is a little different:
'// As the number on Right increases, the number of Left
'// can be made larger
'// Ok, Limit...
Debug.Print [MOD(268435455999,2000)]
'// Error if +1
Debug.Print [MOD(268435456000,2000)]
End Sub

 

[Peter T]

Just be aware that 20% of the time your 'i' value ends in 5.

Just 10% of the time 'i' ends in 5, the other 10% 'i' is divisible by 5 but
ends in zero but was eliminated with the mod 2 check

Numbers that end in 5, ie 25, 35,45, etc are also divisible by 5.

33% of the remaining 10% that end in 5 were eleminated with the mod 3 check.
Roughly 6-7% of all numbers will be eleminated in the third mod 5 check (ie
after Mod 2 and mod 3). The loop exits if i mod 5 = 0, and similarly for all
subsequent loops checking mod with ever increasing 'i' (up to the root of
the number).

Hence, checking 5's is a waste. However, the time involved getting around
this is probably not worth it.

It has be checked if 'i' has already passed the mod 2 & 3 checks.

However in the loop it would not be necessary to check any number that is a
multiple of a number that has already been checked, eg no need to check 9,
15, 21 etc. I haven't put my mind as to how best to skip those numbers
efficiently. Might be worth looking into if anyone needs to check larger
primes, such as in the 'BigPrime' routine below -

It's too bad Microsoft refuses to fix the MOD bug with Excel, even in xl
2007.
One is still limited in vba to the number 2147483647 !!
Sure wish Microsoft would fix this. It would make a lot of code easier to
write.

Debug.Print 2147483647# Mod 2 'Ok
Debug.Print 2147483648# Mod 2 '(Error Limit!)

Maybe the following for those larger than 'Long' numbers

Function BigPrime(num As Double) As Boolean
Dim k As Double
Dim dv As Double

If num < 4 Then
BigPrime = num > 1
ElseIf Int(num / 2) < num / 2 Then
BigPrime = True
k = Int(Sqr(num))
For i = 3 To k Step 2
dv = num / i
If Int(dv) = dv Then
BigPrime = False
Exit For
End If
Next
End If

End Function

At some stage this will give an incorrect result, not sure when though!

Regards,
Peter T