Perl one-liner to check if number is prime

The following Perl one-liner is to show the abilities and power of Perl: in one single line we can tell from a number whether it is a prime or not.

perl -lne '(1x$_) !~ /^1?$|^(11+?)\1+$/ && print "$_ is prime"'

How it works? Let’s see step by step!

perl
Practical Extraction and Report Language

-l (line endings)
The -l switch silently removes the newline character (or whatever $/ is set to, as we will see below) from the end of each line of input, and silently adds a newline character to the end of each line of output. Note that the answers are all reduced by one because each line is shorter by one character: the newline at the end.

-n (implicit looping)
This option is shorthand for while(<>) { }. It wraps your code inside the loop as shown below:

while(<>) {
    # perl code
}

-e (execute, inline scripting)
Execute Perl code in command line itself.

(1x$_)
The number is converted into its unary representation. Say, 6 is converted into 1×6 which is 111111, (1 repeated 6 times).

!~
This operator is the opposite of the =~ operator. Test the previously given unary representation against the following regular expression. If it does not match, the number is a
prime; otherwise it’s a composite (so returns true, if the regular expression does not match).

/^1?$|^(11+?)\1+$/
Regular expression between two slashes ( / ). Consists of two parts separated by | as an OR operator. Let’s see the two parts of the regex separately!

^1?$
The part between ^ and $ signs will be tested from the beginning to the end of the string.
The ? is a metacharacter, which matches the preceding element zero or one time.
Therefor this part of the regex (^1?$) matches 1, or empty string. Since the empty string and 1 are not prime numbers, this part of the regular expression discards them.

^(11+?)\1+$
determines whether two or more 1s repeatedly make up the whole number. If so, the regular expression matches, which means the number is a composite. If not, it’s a prime.

Explanation
Now consider how the second part of the regular expression would act on the number 5. The number 5 in unary is 11111, so the (11+?) matches the first two 1s, the back-reference \1 becomes 11, and the whole regular expression now becomes ^11(11)+$.
Because it can’t match five 1s, it fails. Next, it attempts to match the first three 1s. The back-reference becomes 111, and the whole regular expression becomes ^111(111)+$, which doesn’t match. The process repeats for 1111 and 11111, which also don’t match and as a result the entire regular expression doesn’t match and the number is a prime.

What about the number 4? The number 4 is 1111 in unary. The (11+?) matches the first two 1s. The back-reference \1 becomes 11, and the regular expression becomes ^11(11)+$, which matches the original string and confirms that the number is not prime.

Source: http://www.catonmat.net/blog/perl-one-liners-no-starch-press/

Advertisements