I have no idea who it was that originally came up with the idea of regexes, but I liked it and it seems appropriate here, so:

#!perl -p
$_ x=(1x$_)!~/^(|.|(..+)\2+)$/
[download]

$ seq -50 50 | perl prime.pl
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
[download]