# Tip: Identify a prime number with RegEx

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.

``````(?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``````

Creative solution

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

It would take 4 GB just to hold the test string.

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

I ended up here cause I thought the title said Prime Rib

This should be a pretty close port of one (or more) of the algorithms at
http://rosettacode.org/wiki/MillerRabin_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``````

Since we’ve gone off-track a bit…

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.

Edit: 32G times n, not to the n power.