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