Preprocessing primality

Question

The challenge:

Given an integer N, 1 < N < 2³¹, write code that uses the C preprocessor to determine whether N is prime, and produces a "Hello world" program if N is prime, or an error otherwise. Make the code as short as possible.
It's not very hard, so don't worry that there are so many rules; most of them are boilerplate.

The following sample code (in example.c) works for N < 100:

#include <stdio.h>
int main() {
#if (N%2!=0 && N%3!=0 && N%5!=0 && N%7!=0) || (2==N || 3==N || 5==N || 7==N)
printf("Hello world!");
#else
Walkmen;
#endif
}

23 is prime but 99 is not, so:

c:\golf\preprime>gcc -std=c99 -DN=23 example.c

c:\golf\preprime>a
Hello world!
c:\golf\preprime>gcc -std=c99 -DN=99 example.c
example.c: In function 'main':
example.c:6:1: error: 'Walkmen' undeclared (first use in this function)
 Walkmen;
 ^
example.c:6:1: note: each undeclared identifier is reported only once for each function it appears in
c:\golf\preprime>

Rules

• 1 < N < 2147483648
• N will be defined in a macro named N. N will be written using only the characters 0123456789 and will not begin with 0.
• The code will be compiled with the command gcc -std=c99 -DN=<number> <filename>.c [-o <outfile>]
• If N is prime, a valid C99 program must be successfully compiled. When executed, the program's output to stdout must be precisely Hello world! followed by zero or more newlines.
• If N is composite, gcc must emit a compiler error. A linker error is not acceptable.
• You may not utilize any GCC extensions.
• You may not assume anything about the name of any file.
• Note: It is not allowed to use implicit types or implicit function declarations.
• Neither gcc nor any "Hello world" program may take more than 20 seconds to execute on a typical computer.
• Shortest code length in UTF-8 bytes wins.

For reference, my ungolfed implementation is 571 bytes. Happy golfing!

Answer 1

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

Notes:

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

Answer 2

boost/preprocessor, 355

#ifndef I
#include "boost/preprocessor.hpp"
#include "boost/preprocessor/slot/counter.hpp"
#include "stdio.h"
#define I BOOST_PP_COUNTER
#define F(z,x,d){int a[((x|d<<8)<2||(x|d<<8)==N||N%(x|d<<8))-1];}
int main(){
#include __FILE__
printf("Hello world!");}
#elif I<182
BOOST_PP_REPEAT(256,F,I)
#include BOOST_PP_UPDATE_COUNTER()
#include __FILE__
#endif

boost/preprocessor is part of the boost extension to the standard library for preprocessor programming.

We need both the BOOST_PP_REPEAT and the BOOST_PP_COUNTER + self-include approaches because of the limitations of the system.

gcc only supports a nested include depth of 200, so the counter approach alone is insufficient. BOOST_PP_REPEAT is limited to repeating 256 times, so it doesn't work alone either.

With both approaches together we get up to 51200 repetitions; we need only 46340 (sqrt 2^31) to cover all possible primes.

To actually cause compilation failure we need to generate some code whoses validity depends on primality (since we can't chain together an #if if we're using #includes). The easiest way is to declare an array who's length depends on N%i, since negative array lengths produce a gcc compiler error.

As a bonus the number of error messages is equal to the number of factors :).

Examples

$  gcc -std=c99 -DN=24 primes.c
In file included from primes.c:8:
primes.c: In function ‘main’:
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative
primes.c:11: error: size of array ‘a’ is negative

$  gcc -std=c99 -DN=23 primes.c && ./a.out
Hello world!