I wish I had come up with this, but I read about it here.
You can use a regular expression to determine if a value is a prime number. It’s not the fastest way, but it’s guaranteed to work, and it’s awfully cool.
Here’s the pattern with comments:
(?x) # FREE SPACE MODE
^1?$ # match an empty string (0) or a 1 (1)
| # or
^(11+?)\\g1+$ # match an equal number of groups of "1"
To use it, create a string of “1”'s whose length is the value you are testing, then apply that RegEx. If it matches, the value is not prime.
The code with some optimizations:
Function IsPrime (value As Int64) As Boolean
const kZero as Int64 = 0
const kOne as Int64 = 1
const kTwo as Int64 = 2
if value = kTwo then
return true
elseif value = kZero or value = kOne then
return false
elseif ( value mod 2 ) = 0 then
return false
end if
dim testString as string = Repeat( "1", value ) // Found in StringUtils or M_String
static rxNotPrime as RegEx
if rxNotPrime is nil then
rxNotPrime = new RegEx
rxNotPrime.SearchPattern = "^1?$|^(11+?)\\g1+$"
end if
return rxNotPrime.Search( testString ) is nil
End Function
The theory behind this is so simple, it’s almost childish. A prime number is one that is not a multiple of something else (besides 1). When you convert the value to a series of “1”'s, you will not be able to find an equal groups of “1” in a prime number.
Here are some examples of what the pattern sees and why this works:
5 -> 11111 -> 111 11 # can't find equal groups, so it's prime
9 -> 111111111 -> 111 111 111 # equal groups, it's not prime
15 -> 111111111111111 -> 111 111 111 111 111 # equal groups, so not prime
17 -> 11111111111111111 -> 111111111 11111111 # no equal groups
Interesting solely as curiosity
Expensive in terms of time & space
Trying finding out if something like 4,000,000,001 is prime in a 32 bit app
I suspect it would fail well before that
Hence why I said [quote=331574:@Norman Palardy]Interesting solely as curiosity[/quote]
I’m sure other methods are more time & space efficient than using a regex
This should be a pretty close port of one (or more) of the algorithms at http://rosettacode.org/wiki/MillerRabin_primality_test#Run_BASIC
Public Enum Primality
Composite
Probably_prime
End Enum
Public Function RabinMiller(n as integer, k as integer) as Primality
If n = 2 Then
return Primality.Probably_prime
End If
If n Mod 2 = 0 Or n < 2 Then
Return Primality.Composite
End If
Dim d As Integer = n - 1
Dim s As Integer
Dim base As Integer
Dim x As Integer
Dim r As Integer
While d Mod 2 = 0
d = d / 2
s = s + 1
Wend
While k > 0
k = k - 1
base = 2 + Rnd()*(n-3)
x = pow(base,d) Mod n
If x <> 1 And x <> n-1 Then
For r=1 To s-1
x =(x * x) Mod n
If x=1 Then
Return Primality.Composite
End If
If x = n-1 Then Exit For
Next r
If x<>n-1 Then
Return Primality.Composite
End If
End If
Wend
End Function
I’m thinking of a project that would store all prime numbers up to a given limit in a file whose size is approximately limit / 16. So you could store (or, more accurately, flag) every prime number up to 32G in a file that’s around 2 GB, for example.
This is theoretical and I have no idea if there is a practical use for it, but it’s an interesting experiment, and I wouldn’t be surprised if its already been done. The concept behind it is rather simple.
I’m even less certain of a practical use for that.
But pointing that out made me think that my scheme does not have to be limited to a single file but could be spread over many. So you could flag prime numbers up to 32G^n 32G X n across n 2 GB files.
