Tip: Identify a prime number with RegEx

  1. 3 months ago

    Kem T

    May 18 Pre-Release Testers, Xojo Pro New York

    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. John J

    May 18 Pre-Release Testers, Xojo Pro Cleveland, Ohio

    Creative solution

  3. Norman P

    May 18 Xojo Inc

    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

  4. Kem T

    May 18 Pre-Release Testers, Xojo Pro New York

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

  5. Norman P

    May 18 Xojo Inc

    Hence why I said

    @Norman P Interesting solely as curiosity

    I'm sure other methods are more time & space efficient than using a regex :)

  6. brian f

    May 18 Pre-Release Testers, Xojo Pro Chilly California

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

  7. Norman P

    May 18 Xojo Inc

    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. Kem T

    May 19 Pre-Release Testers, Xojo Pro New York

    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. Jean-Yves P

    May 19 Pre-Release Testers, Xojo Pro Europe (France, Besancon)

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

  10. Kem T

    May 19 Pre-Release Testers, Xojo Pro New York
    Edited 3 months ago by Kem T

    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.

or Sign Up to reply!