Pattern Matching for Primes in Wolfram Language

Here is a Wolfram Language function that takes an integer and checks if it is prime by using the pattern matcher:

In[1]:= patternMatchingPrimeQ[n_] :=
 !MatchQ[Table[blah, n], {Repeated[_, {0, 1}]} | {a:PatternSequence[_, __], a__ ..}]

Check that it agrees with the built-in PrimeQ:

In[2]:= Table[patternMatchingPrimeQ[n], {n, 0, 20}]

Out[2]= {False, False, True, True, False, True, False, True, False, \
False, False, True, False, True, False, False, False, True, False, \
True, False}

In[3]:= Table[PrimeQ[n], {n, 0, 20}]

Out[3]= {False, False, True, True, False, True, False, True, False, \
False, False, True, False, True, False, False, False, True, False, \
True, False}

In[4]:= %% === %

Out[4]= True

How does it work?

This was inspired by a recent post on Hacker News where regex is used to check for primality of a number represented as a unary string.

This is a direct translation of the regex into Wolfram Language pattern matching language and checks the primality of the length of a list using the same technique.

This is not an efficient way to check for primes and I would not recommend checking much beyond 20; it really slows down due to the back-tracking that is necessary.

But pretty cool!