PERL <s>53</s> <s>54</s> <s>52</s> 48
==
<!-- language: lang-perl -->

    ('a'x($_=pop))=~/^a?$|^(?<a>aa+?)\g{a}+$/||print

Thanks to reddit: http://www.reddit.com/r/programming/comments/crmhe/regular_expression_to_check_for_prime_numbers_1111/