Author: Neil Kandalgaonkar

Formatting: Laurent CAPRANI

Look here for a nicer version of this page that Neil made.

I found the actual one-liner Abigail originally used from http://www.mit.edu:8008/bloom-picayune.mit.edu/perl/10138:

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number] |

Cool perl syntax, a statement may have 'modifiers' at the end like this. See `man perlsyn`.

`shift` normally removes the first element of an array and returns that element, like popping from the beginning. Since we are in file scope, `shift` without array is magically interpreted to mean `"shift @ARGV"`, which means the number we fed in as an argument. (see perldoc -tf shift).

`x` is the repetition operator. In this context, `1` is treated as a string `"1"`. If the number was `9`, `"1" x 9` yields `"111111111"`. (see `man perlop`, `grep` for 'repetition operator'.)

The logical negation of `=~`, will succeed if the regex does NOT match. Since we are looking for primes, the regex will should match all NON-primes.

/ ^1?$ # matches beginning, optional 1, ending. | # or... ^ # match beginning of string /x |

To see how it works let's consider the case of N = 9.

1 1 1 1 1 1 1 1 1 |
The ^(11+?) will match two ones at the start, and call it \1. |

1 1 1 1 1 1 1 1 1 |
Next \1+ matches one or more strings identical to \1. |

1 1 1 1 1 1 1 1 1 |
Oops, but the string doesn't end there: backtrack! |

1 1 1 1 1 1 1 1 1 |
no...backtrack! |

1 1 1 1 1 1 1 1 1 |
no...backtrack! |

1 1 1 1 1 1 1 1 1 |
Try matching three ones at the start store it as \1. |

1 1 1 1 1 1 1 1 1 |
Matches 2 more times. |

1 1 1 1 1 1 1 1 1 |
The end of string is next -- match! |

So, you can see how this process is analogous to trying to divide a number by successively larger divisors, leaving no remainder. In the case of a prime number, this is never going to succeed.

BTW: this also is much more efficient than the one I showed the group, with the addition of a single character!

My regex always had to backtrack from the maximal match; since Abigail made the `11+?` match minimal it will start by trying to "divide" the number by 2, then 3, etc. It will reject 32000 instantly, and take somewhat longer to determine that 32003 is prime. A good reminder that backtracking doesn't always reduce the size of a matched portion; with minimal matches it will backtrack and try matching more.

Given the new no-backtrack grouping (`?>`) the useless attempts to match fewer amounts of `\1+` could be eliminated. Benchmarking shows it is slightly faster that way.