模板元編程（英語：Template metaprogramming；縮寫：TMP）是一種元編程技術，不夸張的說，這項技術開啟了一種新的C++編程方式。編譯器使用模板產生暫時性的源碼，然后再和剩下的源碼混合并編譯。這些模板的輸出包括編譯時期常數、數據結構以及完整的函數。如此利用模板可以被想成編譯期的運行。本文介紹了利用模板元編程技術實現在編譯期判斷一個整數是否為素數的算法。輸入為一個大于0的整數，輸出為1表示該整數為素數，為0表示為合數。本文的主要目的是用實例說明模板元編程實現算術和邏輯運算的一般設計和編寫方法。模板元編程的概念和基本介紹參見維基百科：http://zh.wikipedia.org/wiki/模板超編程

我們使用最基本的素數判斷算法，偽代碼如下：

function IsPrime(n) if n == 1 then return false if n == 2 then return true for each m from 2if m * m > n then return trueif n mod m = 0 then return falsem := m + 1

這顯然是一個復雜度為O(sqrt(n))的算法，主要的邏輯為循環。模板元編程是以遞歸的邏輯形式來實現循環算法，因此必須先明確兩件事：有幾個變量參與，以及循環的終止條件是什么。這個算法顯然有2個變量參與運算：一個是n，另一個是m。我們令m從2開始遞增，直到達到循環終止條件。在模板元編程中，由于模板參數推導的優先級是以特化程度排列的，因此終止條件和特殊值的處理使用偏特化（也叫部分特化）實現。關于模板參數推導和偏特化的概念和語法這里不做贅述，請參閱C++書籍或搜索網頁資料。那么根據以上分析，我們可以先寫出一個框架如下：

template<uint n, uint m>struct TEST{const static uint r = TEST<n, nextM>::r; //nextM為下一個M，暫不實現。在這里用遞歸結構代替了循環 }; template<uint n>struct ISPRIME{const static uint r = TEST<n, 2>::r; //從2開始，依次判斷每一個可能的m取值，判斷代碼暫未實現。 }; template<>struct ISPRIME<1>{ //對于算法不能計算的特殊值1，判斷為0const static uint r = 0; }; template<>struct ISPRIME<2>{ //對于算法不能計算的特殊值2，判斷為1const static uint r = 1; };

循環的終止條件是：m的平方大于n或可以整除n。當滿足終止條件時，向模板參數傳遞一個特殊值，并在偏特化中處理這個值，那么遞歸邏輯就終止了。而判斷是否滿足終止條件，則需進行邏輯和算術運算?；谝陨戏治?#xff0c;框架代碼改寫如下：

template<uint n, uint m>struct TEST{// if (n % m == 0) n = 0;// if (m * m > n) m = 0; else ++m;const static uint r = TEST<n, m>::r; //上面兩行代碼不能寫在此處，僅說明邏輯。實際的語法下文再做介紹 }; template<uint m>struct TEST<0, m>{ //n為0的情況const static uint r = 0; //即在非特化的模板代碼中，n可以被m整除，因此n被賦值為0，故為合數 }; template<uint n>struct TEST<n, 0>{ //m為0的情況const static uint r = 1; //即在非特化的模板代碼中，m * m > n，因此n不能被任何比它小的數整除，故為素數 }; template<uint n>struct ISPRIME{const static uint r = TEST<n, 2>::r; //從2開始，依次判斷每一個可能的m取值，判斷代碼暫未實現。 }; template<>struct ISPRIME<1>{ //對于算法不能計算的特殊值1，判斷為0const static uint r = 0; }; template<>struct ISPRIME<2>{ //對于算法不能計算的特殊值2，判斷為1const static uint r = 1; };

?最后只要用模板的參數推導實現取模的算術運算和上面框架中的兩個邏輯判斷即可，完整代碼如下：

#include <iostream> typedef unsigned int uint;template<uint n, uint m>struct NEXTN{const static uint r = ((n % m != 0) * n); };template<uint n, uint m>struct NEXTM{const static uint r = (m * m <= n ? (m + 1) : 0); };template<uint n, uint m>struct TEST{const static uint r = TEST<NEXTN<n, m>::r, NEXTM<n, m>::r>::r; };template<uint m>struct TEST<0, m>{const static uint r = 0; };template<uint n>struct TEST<n, 0>{const static uint r = 1; };template<uint n>struct ISPRIME{const static uint r = TEST<n, 2>::r; };template<>struct ISPRIME<1>{const static uint r = 0; };template<>struct ISPRIME<2>{const static uint r = 1; };int main() {int primes[] = {ISPRIME<1>::r, ISPRIME<2>::r, ISPRIME<3>::r, ISPRIME<4>::r,ISPRIME<5>::r, ISPRIME<6>::r, ISPRIME<7>::r, ISPRIME<8>::r,ISPRIME<9>::r, ISPRIME<10>::r, ISPRIME<11>::r, ISPRIME<12>::r,ISPRIME<13>::r, ISPRIME<14>::r, ISPRIME<15>::r, ISPRIME<16>::r,};for (int i = 0; i < sizeof(primes) / sizeof(primes[0]); ++i)std::cout << i + 1 << (primes[i] ? " YES" : " NO") <<std::endl;return 0; }

?如果您有更簡潔的寫法，請回復告知。謝謝！

轉載于:https://www.cnblogs.com/devymex/p/3326793.html

總結

以上是生活随笔為你收集整理的模板元编程实现素数判定的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。