Imported the original cryp.to site for re-publishing with ikiwiki.
[cryp.to.git] / prime-sieve.mdwn
1 [[!meta title="C++ compile-time prime sieve"]]
2 [[!tag cxx-riddle]]
3
4     /*
5      * prime-sieve.cpp
6      *
7      * This code implements the Sieve of Erathostenes in meta templates.
8      * The type prime_sieve<n>::result expands to a list of integers that
9      * represents the primes in [2..n]. This list of primes is computed
10      * entirely at compile-time. The short example main() program at the
11      * end demonstrates how to access that list.
12      */
13
14     //////////////////////////////////////////////////////////////////////
15     // Meta-programming Infrastructure
16     //////////////////////////////////////////////////////////////////////
17
18     struct nulltype { };
19
20     template<typename head, typename tail>
21     struct typelist { };
22
23     template<unsigned int i>
24     struct integer
25     {
26       enum { value = i };
27     };
28
29     template<bool cond, typename true_type, typename false_type>
30     struct ifelse
31     {
32       typedef true_type result;
33     };
34
35     template<typename true_type, typename false_type>
36     struct ifelse<false, true_type, false_type>
37     {
38       typedef false_type result;
39     };
40
41     //////////////////////////////////////////////////////////////////////
42     // Alorithm to create [i..n]
43     //////////////////////////////////////////////////////////////////////
44
45     template<unsigned int i, unsigned int n>
46     struct integer_range
47     {
48       typedef typelist< integer<i>, typename integer_range<i+1, n>::result > result;
49     };
50
51     template<unsigned int n>
52     struct integer_range<n, n>
53     {
54       typedef typelist< integer<n>, nulltype > result;
55     };
56
57     //////////////////////////////////////////////////////////////////////
58     // Sieve of Erathostenes
59     //////////////////////////////////////////////////////////////////////
60
61     template<unsigned int i, typename integers>
62     struct sieve_multiples_of;
63
64     template<unsigned int i, typename x, typename xs>
65     struct sieve_multiples_of< i, typelist<x,xs> >
66     {
67       typedef typename ifelse
68         < x::value % i != 0u
69         , typelist<x, typename sieve_multiples_of<i, xs>::result>
70         , typename sieve_multiples_of<i, xs>::result
71         >::result result;
72     };
73
74     template<unsigned int i>
75     struct sieve_multiples_of<i, nulltype>
76     {
77       typedef nulltype result;
78     };
79
80     template<typename integers>
81     struct sieve_list;
82
83     template<typename x, typename xs>
84     struct sieve_list< typelist<x,xs> >
85     {
86       typedef typelist<x, typename sieve_list<typename sieve_multiples_of<x::value, xs>::result>::result> result;
87     };
88
89     template<>
90     struct sieve_list<nulltype>
91     {
92       typedef nulltype result;
93     };
94
95     template<unsigned int n>
96     struct prime_sieve
97     {
98       typedef typename sieve_list<typename integer_range<2,n>::result>::result result;
99     };
100
101
102     //////////////////////////////////////////////////////////////////////
103     // Copy a type list to an output iterator
104     //////////////////////////////////////////////////////////////////////
105
106     template<typename typelist>
107     struct copy_list;
108
109     template<typename x, typename xs>
110     struct copy_list< typelist<x,xs> >
111     {
112       template<typename output_iterator>
113       static output_iterator to(output_iterator i)
114       {
115         *i = x::value;
116         return copy_list<xs>::to(++i);
117       }
118     };
119
120     template<>
121     struct copy_list<nulltype>
122     {
123       template<typename output_iterator>
124       static output_iterator to(output_iterator i)
125       {
126         return i;
127       }
128     };
129
130     //////////////////////////////////////////////////////////////////////
131     // Compute the primes in [2..100] and write them to standard output
132     //////////////////////////////////////////////////////////////////////
133
134     #include <iostream>
135     #include <iterator>
136
137     int main(int, char**)
138     {
139       using std::ostream_iterator;
140       using std::cout;
141       using std::endl;
142
143       enum { n = 100 };
144       typedef prime_sieve<n>::result primes;
145
146       cout << "Primes found in [2.." << n << "]:" << endl;
147       copy_list<primes>::to(ostream_iterator<unsigned int>(cout, " "));
148       cout << endl;
149
150       return 0;
151     }