C言語で婚約数を判定する方法をわかりやすく解説

婚約数（Betrothed Numbers）とは？

婚約数（betrothed numbers）とは、2つの整数のペアのうち、一方の数の約数の総和（その数自身を除く）に1を加えると、もう一方の数と等しくなるような関係を持つ数のペアのことです。

具体的には、(a, b) が婚約数のペアであるためには、s(a) = b + 1 かつ s(b) = a + 1 が成り立つ必要があります。ここで s(n) は、n 自身を除く約数の総和（アリコット和）を表します。この条件は、約数関数 σ を使って「σ(a) = σ(b) = a + b + 1」という形でも表現できます。

婚約数として知られている最初のいくつかのペアは以下の通りです。

(48, 75)、(140, 195)、(1050, 1925)、(1575, 1648)、(2024, 2295)、(5775, 6128)

興味深いことに、現在知られているすべての婚約数のペアは偶奇性が異なっています（片方は偶数、もう片方は奇数）。もし同じ偶奇性を持つペアが存在するならば、それは 10¹⁰ を超える非常に大きな数になると考えられています。

判定アルゴリズム

ステップ1：両方の数について、約数の総和を求める。
ステップ2：一方の数の約数の和に1を加えた値が、もう一方の数と一致するかどうかを確認する。
ステップ3：一致すれば婚約数、そうでなければ婚約数ではない。

実行例

入力: a = 48, b = 75
出力:
48 と 75 は婚約数です

処理の流れの解説

まず、48 の約数を列挙すると「1, 2, 3, 4, 6, 8, 12, 16, 24」となり、その総和は 76 になります。

次に、75 の約数を列挙すると「1, 3, 5, 15, 25」となり、その総和は 49 になります。

C言語では for ループを使い、1 から a - 1 までの各数値を順番に調べます。ループ内で、その数値が a を割り切れるかどうかを判定し、割り切れる場合は変数 aDivisorSum に加算していきます。ループが完了した時点で、aDivisorSum には a のすべての約数の和が格納されています。

同じ手順で、もう一方の数の約数の総和も求めて bDivisorSum に保存します。

最後に、「一方の数に1を加えた値が、もう一方の数の約数の和と一致するか」を確認します。条件を満たしていれば両者は婚約数であると出力し、満たしていなければ婚約数ではないと出力します。

C言語による実装例

#include <stdio.h>
int main() {
    int i;
    int a,b;
    int aDivisorSum = 0;
    int bDivisorSum = 0;
    a=48 ;
    b=75 ;
    for( i = 1; i < a; i++) {
        if(a % i == 0) {
            aDivisorSum = aDivisorSum + i;
        }
    }
    for( i = 1; i < b; i++) {
        if(b % i == 0) {
            bDivisorSum = bDivisorSum + i;
        }
    }
    if(( a+1== bDivisorSum) && (b+1 == aDivisorSum)) {
        printf("%d and %d are Betrothed numbers\n",a,b);
    } else {
        printf("%d and %d are not Betrothed numbers\n",a,b);
    }
}

実行結果

48 and 75 are Betrothed numbers

このように、48 の約数の和（76）は 75 + 1 と一致し、75 の約数の和（49）は 48 + 1 と一致するため、(48, 75) は婚約数のペアであることが確認できます。