//
// A C++ program to test for the primality of the number 13
//
// It has the curious property that it does no arithmetic
// but uses only the template mechanism and class derivation
// to achieve its result. It starts at the most basic axioms
// of arithmetic starting with the definition of zero and
// its successors...
//
// You'll need a good C++ compiler.
//
// (c) D Piponi (But copy it as much as you like if you credit me)
//

//
// First a little trick to find the base class of our
// classes because the template mechanism requires
// exact matches.
//
// Two values are considered equivalent if they have
// the same baseclass. For example 1+1 isn't
// identical to 2 but 1+1 *is* derived from 2.
//
template<typename V> struct Value { typedef V value; };

//
// Define zero
//
struct zero
       : public Value<zero> { };

//
// Define the successor of an integer
//
template<typename C> struct S
       : public Value<S<C> > { typedef C predecessor; };

//
// Now we have the integers. So introduce some convenience
// types.
//
typedef S<zero> one;
typedef S<one> two;
typedef S<two> three;
typedef S<three> four;
typedef S<four> five;
typedef S<five> six;
typedef S<six> seven;
typedef S<seven> eight;
typedef S<eight> nine;
typedef S<nine> ten;

//
// Define plus,...
//
template<typename C,typename D> struct plus
  : public S<plus<C,typename D::predecessor> > { };

template<typename C> struct plus<C,zero>
       : public C { };

//
// ...minus...
//
template<typename C,typename D> struct minus
       : public minus<C,typename D::predecessor>::predecessor { };

template<typename C> struct minus<C,zero>
       : public C { };

//
// ...and times.
//
template<typename C,typename D> struct times
       : public plus<C,typename times<C,typename D::predecessor>::value> { };

template<typename C> struct times<C,zero>
       : public zero { };

//
// Define the usual ordering on the integers.
//
template<typename C,typename D> struct ge
       : public ge<typename C::predecessor,typename D::predecessor> { };

template<typename C> struct ge<C,zero>
       : public one { };

template<typename C> struct ge<zero,C>
       : public zero { };

template<> struct ge<zero,zero>
       : public one { };

//
// Divisibility testing
//
template<typename C,typename D,typename E = S<S<zero> > > struct Divisible { };

template<typename C,typename D> struct Divisible<C,D,S<S<zero> > >
       : public Divisible<C,D,typename ge<C,D>::value> { };

//
// The case C<D:
// In this case D divides C iff C is zero.
//
template<typename C,typename D> struct Divisible<C,D,zero>
       : public zero { };

template<typename C> struct Divisible<zero,C,zero>
       : public one { };

//
// The case C>=D:
// D divides C iff D divides C-D.
//
template<typename C,typename D> struct Divisible<C,D,S<zero> >
       : public Divisible<typename minus<C,D>::value,D> { };

//
// Primality testing
//
template<typename C,typename D = two,typename S = zero,typename E = zero,typename F =
zero> struct Prime { };

//
// We use recursion to set up a loop from 2 to one less
// than the integer we are testing. Essentially this is a state machine
// using template parameters to record the current state.
//

// Are we at the end of the recursion?
//
template<typename C,typename D> struct Prime<C,D,zero,zero,zero>
       : public Prime<C,D,one,zero,typename ge<D,C>::value> { };

//
// Test potential factor D, trying successor on failure.
//
template<typename C,typename D> struct Prime<C,D,one,zero,zero>
       : public Prime<C,S<D>,zero,typename Divisible<C,D>::value,zero> { };

//
// Found a factor.
//
template<typename C,typename D> struct Prime<C,D,zero,one,zero>
       : public zero { };

//
// Reached the end of the loop without finding divisor.
//
template<typename C,typename D> struct Prime<C,D,one,zero,one>
       : public one { };

//
// Convenience method for humans allowing input of
// numbers in decimal format.
//
template<typename C,typename D> struct Decimal
       : public plus<typename times<ten,C>::value,D> { };

//
// Unfortunately the I/O interface spoils the purity of it all.
//
#include <stdio.h>

template<typename C> char *output(C);

template<> char *output(zero) { return "No"; }

template<> char *output(one) { return "Yes"; }


main() {
   //
   // Is 13 prime?
   //
   puts(output(Prime<Decimal<one,four>::value>::value()));
}