Determine if a number is prime without using arithmetic
PHP, 117 characters

This one is based on regular expressions. If a string containing $n characters can be split into chunks of equal length, then $n must be composite.

(Assumes $n is a positive integer.)

function p($n){$u=true;$s=str_repeat('x',$n);return($s!='x'&amp;&amp;!preg_match('/^(xx{'.$u.',})\\'.$u.'{'.$u.',}$/U',$s));}


Output:

for ($i=1; $i&lt;=100; $i++) if (p($i)) echo "$i ";

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97