Tip: Identify a prime number with RegEx

Off-Topic
#1

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
#2

Creative solution

#3

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 :slight_smile:
I suspect it would fail well before that

#4

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

#5

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 :slight_smile:

#6

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

#7

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
#8

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.

#9

https://en.wikipedia.org/wiki/Largest_known_prime_number

#10

I’m even less certain of a practical use for that. :slight_smile:

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.

#11