Jserv's blog

以 C++ template meta-programming 來實現 Sieve of Eratosthenes

Peter Simons 做了一個展示，用 C++ template meta-programming 來實現 [Sieve of Eratosthenes]，可參考 [prime-sieve.cc]。[Sieve of Eratosthenes] 是古典數學中用以求質數相當經典且簡單的途徑，不需要太多解釋，直接觀看 Wikipedia 的圖解就可知悉其演算法：

而，運用 C++ template meta-programming 可用更直覺的方式來「描述」該演算法，試看以下程式列表：

//////////////////////////////////////////////////
// Alorithm to create [i..n]
//////////////////////////////////////////////////

template<unsigned int i, unsigned int n>
struct makeIntList
{
        typedef Typelist< IntType<i>, typename makeIntList<i+1, n>::Result > Result;
};
template<unsigned int n>
struct makeIntList<n, n>
{
        typedef Typelist< IntType<n>, NullType > Result;
};
//////////////////////////////////////////////////
// The Sieve of Erathostenes
//////////////////////////////////////////////////

template<unsigned int i, typename TList>
struct sieveOne;
template<unsigned int i, typename x, typename xs>
struct sieveOne< i, Typelist<x,xs> >
{
        typedef typename Select<

                x::value % i != 0,
                Typelist< x, typename sieveOne<i, xs>::Result >,
                typename sieveOne<i, xs>::Result
                        >::Result    Result;
};
template<unsigned int i>
struct sieveOne<i, NullType>
{
        typedef NullType Result;
};
template<typename TList>
struct sieveAll;
template<typename x, typename xs>
struct sieveAll< Typelist<x,xs> >
{
        typedef Typelist<
                x,
                typename sieveAll<typename sieveOne<x::value, xs>::Result>::Result
                        >     Result;
};
template<>
struct sieveAll<NullType>
{
        typedef NullType Result;
};
template<unsigned int n>
struct primeSieve
{
        typedef typename sieveAll<typename makeIntList<2,n>::Result>::Result Result;
};

整個演算法被包裝成 template object，其中可看到試除的過程，最後我們再設計可一一讀取 Result 的 iterator。當代入[2..20]，可得以下輸出：

$ ./prim-sieve 
Finding prime numbers in [2..20]:
2 3 5 7 11 13 17 19

令人驚豔的優雅！
由 jserv 發表於 August 20, 2006 02:50 PM