Hacker News new | past | comments | ask | show | jobs | submit login

For real?

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



I guess you mean "For real?" as in "Is this really a primality test?" Yes, it is, and Krumins describes how it works in the post that I linked (http://www.catonmat.net/blog/perl-regex-that-matches-prime-n...).

Essentially, although it looks complicated, it's the simplest possible idea: it's just trying factorisations, with the `(11+?)` part being the factor, and the `\1+` part insisting that we repeat that factor. It is of course wildly inefficient, and limitations in the backtracking engine mean that it can give false positives for large numbers (http://zmievski.org/2010/08/the-prime-that-wasnt, also linked from that post).


I prefer the Perl 6 version, it's self-documenting:

    perl6 -n -e 'say "$_ is prime" if (+$_).is-prime'




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: