Is there a formula for identifying prime numbers in Excel?
"Dana DeLouis" wrote in message
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.
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
|