A regular expression to check for prime numbers (2007)
I&#x27;ll be &quot;that guy&quot; -- this is <i>not</i> a regular expression [1].  A Perl regexp, sure.  But backreferences are not part of the grammar of regular expressions, and moreover, using them in that particular manner (to refer to a capture of unbounded length) cannot be encoded as a DFA and therefore does not describe a regular language.<p>(I have no clue whether unary-representation primality is actually regular or not -- it&#x27;s been far too long since my automata class to remember how to (dis)prove that -- but I guess it&#x27;s at least sublinear, since primality is polynomial w&#x2F;r&#x2F;t the logarithm of the number being tested.)<p>[1] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Regular_expression#Formal_definition" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Regular_expression#Formal_defi...</a>