Preprocessing primality
441 characters

OK, here is another approach — this time breaking things down into a giant binary tree of tests. I was hoping this could be done recursively, but the C preprocessor doesn't support recursive functions...so I did this as a fallback.

Algorithm: This tests N for divisibility by 2 and by all odd numbers up to the square root of 2³². (Note: That's a bit of overkill, because it need only test potential divisors up to the square root of 2³¹, but it's easier to stick to powers of 2.)

#define A(x) (N%(x)||N==x)
#define B(x) A(x)&amp;A(x+2)&amp;A(x+4)&amp;A(x+6)
#define C(x) B(x)&amp;B(x+8)&amp;B(x+16)&amp;B(x+24)
#define D(x) C(x)&amp;C(x+32)&amp;C(x+64)&amp;C(x+96)
#define E(x) D(x)&amp;D(x+128)&amp;D(x+256)&amp;D(x+384)
#define F(x) E(x)&amp;E(x+512)&amp;E(x+1024)&amp;E(x+1536)
#define G(x) F(x)&amp;F(x+2048)&amp;F(x+4096)&amp;F(x+6144)
#define H(x) G(x)&amp;G(x+8192)&amp;G(x+16384)&amp;G(x+24576)
#include &lt;stdio.h&gt;
int main(){
#if A(2)&amp;H(3)&amp;H(32771)
printf("Hello world!");
#else
Walkmen;
#endif
}


Notes:


The value 32771 is really just 3+32768.
Yes, the parentheses around x in N%(x) are indeed needed (but not in N==x).
Compiles as per instructions and obeys rules of output.
Elapsed time for each test of N (e.g., each invocation of the compiler) is about 1/6 second on my machine.