++$";while($\=$/and$"++and$;=$"){
do{$;&=$|and last if!($"%$_)}for@_;
push@_,$"and print$"if$;}
[download]

Okay, this one I'll explain for those that are curious.

There are two normal ways of calculating prime numbers - the sieve of eratosthenes and by checking all divisors. The sieve works by taking a list of numbers (say 1-500) and marking off all multiples. So you start with "2", and mark off 4, 6, 8, 10, 12, 14 and so on. Then you go to 3 and mark off 9 (6 was already marked off), 15, and so on. It's very very fast.

The other normal way is to check all possible divisors. So if you want to see if 14 is prime, you divide it by 2,3,4,5,6,7,8,9,10,11,12,13. If any of those go into it evenly, it's not prime and you skip it. if none of them do, it's prime and you're done.

The first optimization that most CS 102 students add in for this problem (it's a standard intro to CS task) is to cleverly check only up to NUMBER / 2. Because your lowest multiplier is always 2, if the multiplicand is greater than half of your number, then the product will always be higher. Now we're only checking to see if 14 is divisible by 2,3,4,5,6,7. Cut our work in half.

The next step to optimize the process is to realize that the multiplier can never be greater than the square root of the number. The square root times any number smaller than it will be smaller than the number you're checking, and the square root times any number greater it will be greater than the number you're checking. The square root of 14 is 3.74165, so we can get away with only checking 2 and 3. Much less work.

Most people stop here, but there's another step you can take. You actually only need to check all of the prime numbers that are less than the square root. For example, if the number is 64, you don't need to check and see if 64 / 8 (which it is) because you know that 8 is divisible by 2. So if 8 divides into 64, you know for a fact that 2 divides it as well. So only checking the primes radically decreases your count. In the example of 14, it's still only 2, and 3. For 64, instead of checking 2,3,4,5,6,7,8 you would now only check 2,3,5,7. (Note that it bombs out at 2 anyway).

There's a additional trick I know that I rarely use. You can take the number mod 6. Prime numbers mod 6 are only either 1 or 5, never the others. Breaking it down, if X % 6 is...

remainder	X is divisible by
0	6
1	(unknown)
2	2
3	3
4	2
5	(unknown)

There may be other modulus tricks along these lines.

Now for how this script operates.

First, we'll re-format it into something easier on the eyes.

++$";
while($\= $/ and $"++ and $;=$" ) {
    do{
        $; &= $| and last if ! ($" % $_)
    } for @_;
    push @_, $" and print $" if $;
}
[download]

We arbitrarily choose to use some built in "noisy" variables to make it more obfuscated. We start off by incrementing $". That's normally empty, so that sets it to 1. $" will be our number that we're checking for primeness

Entering our while loop, we have:

while($\= $/ and $"++ and $;=$" ) {
[download]

The first step is just there to confuse you - it sets the output record separator to the input record separator ("\n" on unix systems) to allow the output to have linebreaks. This could easily be before the loop. Next, we increment $". Since it's already 1 (not prime), we start checking at 2. Finally, we use $; as our "break" operator and arbitrarily set it to $", which is a known true value.

    do{
        $; &= $| and last if ! ($" % $_)
    } for @_;
[download]

Here's where the work is done. @_ is going to contain the list of all prime numbers we've found so far. This is that final optimization listed up above - we're only going to check the primes less than our current number. We discard the optimization of looking up through to the square root for compactness purposes.

And it's easy. Check every prime. If the number we're checking ($") modulus the prime we're looking at ($_) is 0, then the number is not prime. In that case, set our arbitrary true value ($;) to something false. We do this by $; &= $|, since $| is normally set to false. We then escape from the loop. The if ! is more clearly written as an unless.

push @_, $" and print $" if $;
[download]

Finally, if our arbitrary true value ($;) is still true (meaning, we found no successful divisors), then it's prime. So we add it to the stack of primes (@_) and print it out. Wash, rinse, repeat.