2.3. パリティ
数を分類する最も単純な方法は、おそらく偶数と奇数に分けることでしょう。この偶数と奇数の区別（偶奇性）のことをパリティと言います。定義により、2では割り切れる数はすべて偶数、2で割りきれない数は奇数となります。例えば、2、4、100、5000はすべて偶数であり、1、3、51、277はいずれも奇数です。偶数と奇数には、同等の2進形式に変換した場合に現れる興味深い性質があります。2進形式に変換すると、その数が偶数の場合は最下位桁が必ず0になり、奇数の場合は最下位桁が必ず1になるのです。そのため、数を2進形式で表せば、その数が偶数と奇数のどちらであるかを容易に判定することができます。
4 = 1002 9 = 10012 20 = 101002 23 = 101112
2つの整数が両方とも偶数または両方とも奇数である場合、その2つの数のパリティは一致します。そうでない場合は、相反するパリティを持ちます。
以下に、数のパリティを調べるためのコードを示します。
// check number is even or not template <int u> struct IsEven { enum { value = Divisible<u, 2>::value }; }; // check number is odd or not template <int u> struct IsOdd { enum { value = Divisible<u, 2>::value == 0 ? 1 : 0 }; };
数が持つこの単純な特性（パリティ）は、データ通信において伝送中のエラーをチェックするために活用されています。このエラーチェックを使用する場合は、データを相手方に送信する前に、偶（even）と奇（odd）のどちらのパリティを使用するかを選択し、バイト内の1ビットをこのパリティのために確保しておく必要があります。そしてビットの個数の偶奇とパリティが一致すればパリティビットを1に設定し、一致しなければ0に設定します。例えば、偶のパリティを選択した場合は、データ内のビットの個数が偶数ならばパリティビットをオンにし、奇数ならばオフにします。奇のパリティを選択した場合は、パリティビットをまったく逆に設定することになります。
データの伝送中または伝送後に、データの1つのビットがなんらかの理由で本来とは逆の状態に変化してしまった場合、受信側ではパリティビットを利用したチェックによってその誤りを検出することができます。ただし、この単純なチェックではエラーの発生を検出できるだけで、エラーを訂正することはできません。また、このチェック方法では、奇数個のビットの状態が変化した場合はエラーを検出できますが、偶数個のビットで誤りが発生した場合はエラーを検知できません。
2.4. 最大公約数の計算
どちらも0ではない2つの整数aとbの最大公約数（GCD）とは、aとbの両方を割り切れる最大の整数のことです。最大公約数は「最大共通因数（HCF）」と呼ばれることもあります。uとvの最大公約数は次のように表すことができます。
k = gcd(u, v)
また、次のように表すこともできます。
gcd(u, v) = max { k | k \ u and k \ v}
この式のk \ uはuがkで割り切れることを意味し、k \ vはvがkで割り切れることを意味します。
1つの整数が0である場合の最大公約数については、慣例的に次の式を使用します。
gcd(u, 0) = u
gcd(0, 0)は定義されていません[4]。
ユークリッドのアルゴリズムは、2数の最大公約数を計算するための最古のアルゴリズムです。これは現在でも誤りなく結果を求めるために使用できる最も古いアルゴリズムの1つであると言えるかもしれません。このアルゴリズムは対象の2つの数がいずれも正の整数であることを前提としています。
負でない任意の整数uとvの最大公約数は、次の関係を再帰的に適用することによって計算できます。
gcd(u, v) = gcd(v, u mod v) // calculate gcd template <int u, int v> struct gcd { enum { value = gcd<v, u % v>::value }; }; template <int u> struct gcd<u, 0> { enum { value = u }; }; template <> struct gcd<0, 0> { enum { value = -1 }; };
2つの整数aとbを座標とする平面上の点(a, b)と原点を直線で結ぶと、その2つの数の最大公約数は、この直線上で原点に最も近い格子点によって表されます。この格子点のx座標とy座標は、それぞれaとbをその最大公約数で割った値になります。
2.5. 最小公倍数の計算
最小公倍数（LCM）とは、両方の数の倍数である（0ではない）最小の数のことです。最小公倍数は「最小公分母（LCD）」と呼ばれることもあります。
最小公倍数は次の式で定義できます。
lcm(u, v) = min { k | k > 0, u \ k and v \ k}
この式のu \ kはkがuで割り切れることを意味し、v \ kはkがvで割り切れることを意味します。
最大公約数（GCD）と最小公倍数（LCM）の間には次のように密接な関係があります。
gcd(u, v) * lcm(u, v) = u * v // calculate lcm template <int u, int v> struct lcm { enum { value = u * v / gcd<u, v>::value }; };
2.6. 互いに素な数
2つの数が1以外の共通因数を持たない場合、その2つの数は「互いに素である」と言います。つまり、2つの数の最大公約数が1であるならば、それらの数は互いに素であると言えます。
// check if numbers are coprime (relative prime) or not template <int u, int v> struct CoPrime { enum { value = gcd<u, v>::value == 1 ? 1 : 0 }; };
2つの数が互いに素であるとすると、幾何学的には、その2つの数がそれぞれx座標とy座標である平面上の点と原点を直線で結んだ場合、その直線上には両端の点以外には格子点が1つも存在しません。2つの数が互いに素でないならば、その直線は途中で格子点を通過し、その中で原点に最も近い格子点によって2数の最大公約数が示されます。
2.7. 素数
任意の自然数が1とその数自体の2つしか約数を持たない場合、その自然数は「素数」と呼ばれます。素数を小さいものから順番に5つ挙げると、2、3、5、7、11となります。4、6、9などのように3個以上の約数を持つ数は「合成数」と呼ばれます。「1」は約数を1つしか持たないので、素数と合成数のどちらとも見なされません。
すべての数は素数の積として表すことができます。このことに関して注意すべき重要な点は、ある数を素数の積として表す方法は1とおりしか存在しないことです。言い換えれば、ある数を素因数に分解することによって得られる素数の集合は常に一意的です。次に素因数分解の例を示します。
100 = 2 * 2 * 5 * 5 4235 = 5*7*11*11
すべての自然数を一意的に素因数分解できることは「算術の基本定理」として知られています。
// check the given number is prime or not template <int n> struct IsPrime { enum { value = NoOfDivisor<n>::value == 2 ? 1 : 0 }; };
約数の個数を調べるNoOfDivisor関数の定義については「3.1. 因数の個数」を参照してください。
