3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ Nice. It's not required to write "Walkmen" :) \$\endgroup\$ – feersum Oct 3 '14 at 23:40
3
\$\begingroup\$

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!
\$\endgroup\$
  • \$\begingroup\$ Genius. Especially the 200*256 > √2³¹ part. \$\endgroup\$ – Todd Lehman Oct 4 '14 at 20:06
  • \$\begingroup\$ Love the self-inclusion. I tried N = 1338557220 for 18 MB of errors. \$\endgroup\$ – feersum Oct 5 '14 at 10:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.