テンプレートプログラミング例2素数判定
8743 ワード
原理
最も基本的な素数判定アルゴリズムは、以下の通りです.
function Is Prime(n)
if n==1 then return false
if n==2 then return true
for each m from 2
if m*m>n then return true
if n mod m=0 then return false
m:=m+1
複雑度はO(sqrt(n)のアルゴリズムで、主な論理は循環です.
テンプレート要素プログラミングは再帰的論理形式で循環アルゴリズムを実現する.
まず二つのことを明確にしなければなりません.いくつかの変数が参加し、循環の終了条件は何ですか?このアルゴリズムは明らかに2つの変数が演算に参加しています.一つはnで、もう一つはmです.私たちはmを2から増やして、循環終了条件に達するまでにします.
基本フレーム
終了条件を満たすと、テンプレートパラメータに特別な値を渡し、この値を偏差特化で処理すると、再帰論理は終了する.終了条件を満たしているかどうかを判断するには、論理と算術演算が必要です.
書き換えたフレーム
テンプレートのパラメータで導出すれば、型取りの算術演算と上のフレームの2つの論理判定が可能です.
最も基本的な素数判定アルゴリズムは、以下の通りです.
function Is Prime(n)
if n==1 then return false
if n==2 then return true
for each m from 2
if m*m>n then return true
if n mod m=0 then return false
m:=m+1
複雑度はO(sqrt(n)のアルゴリズムで、主な論理は循環です.
テンプレート要素プログラミングは再帰的論理形式で循環アルゴリズムを実現する.
まず二つのことを明確にしなければなりません.いくつかの変数が参加し、循環の終了条件は何ですか?このアルゴリズムは明らかに2つの変数が演算に参加しています.一つはnで、もう一つはmです.私たちはmを2から増やして、循環終了条件に達するまでにします.
基本フレーム
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, 0
const static uint r = 0;
};
template<>struct ISPRIME<2>{ // 2, 1
const static uint r = 1;
};
サイクルの終了条件は、mの平方がnより大きいか、またはnを整除することができることである.終了条件を満たすと、テンプレートパラメータに特別な値を渡し、この値を偏差特化で処理すると、再帰論理は終了する.終了条件を満たしているかどうかを判断するには、論理と算術演算が必要です.
書き換えたフレーム
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, 0
const static uint r = 0;
};
template<>struct ISPRIME<2>{ // 2, 1
const static uint r = 1;
};
実現するテンプレートのパラメータで導出すれば、型取りの算術演算と上のフレームの2つの論理判定が可能です.
#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;
}
:http://coolshell.cn/articles/3738.html#more-3738