友愛数を求めるプログラム

友愛数を求めるプログラムを作ったので簡単な解説と一緒に載せておきます。実行環境はVisual Studio Community 2022バージョン17.10.1です。

概要

友愛数とは、異なる2つの自然数の組で、自分自身を除いた約数の和が互いに等しい数のことです。例えば、
220の自分自身を除いた約数の和は

1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284

284の自分自身を除いた約数の和は

1 + 2 + 4 + 71 + 142 = 220

なので互いに等しいため、220と284は友愛数となります。

コード

友愛数を求めるC++20のコードを以下に記載しています。

Amicable.cpp

#include <iostream>

//自分自身を除いた約数の和を求める関数
long long sum_divisor(long long x)
{
	long long sum = 1; //約数の合計を入れる変数

	for (long long i = 2; i * i <= x; i++)
	{
        //余りが0なら約数なので加算する
		if (x % i == 0)
		{
			if (i * i == x)
			{
				sum += i;
			}
			else
			{
				sum += i;
				sum += x / i;
			}
		}
	}

	return sum;
}

int main()
{
	long long n; //nまでの友愛数を探す
	std::cin >> n; //nを入力

	for (long long i = 2; i <= n; i++)
	{
		long long j = sum_divisor(i); //整数iの約数の合計を求める

        //友愛数の判定を行う
		if (sum_divisor(j) == i && i < j)
		{
			std::cout << i << ", " << j << std::endl;
		}
	}
}

自然数$x$の約数の和を求める関数sum_divisorに関してですが、1は必ず約数に含まれるので合計値を入れる変数sumを1で初期化します。
次に自然数を2から順番に$x$を割り切ることができるか探索します。割り切れたら合計値sumに追加します。この時sumに約数と$x$をその約数で割った商を同時に加算します。こうすることでループの範囲を$x$の平方根以下までに抑えられます。
ここで気を付けないといけないのは$i × i = x$が成立する場合です。約数と商が等しいため、同じ約数が重複して加算されます。なのでif文を使って場合分けをしました。
main関数の中では入力した値$n$までの友愛数を求めます。
友愛数判定のif文の中でi < jを追加していますが、これがないと同じ数字の組が重複して出力されたりするので気を付けましょう。
以下が100000までの友愛数の出力の結果です。

220, 284
1184, 1210
2620, 2924
5020, 5564
6232, 6368
10744, 10856
12285, 14595
17296, 18416
63020, 76084
66928, 66992
67095, 71145
69615, 87633
79750, 88730

C#とPythonの友愛数を求めるコードも載せておきます。バージョンはそれぞれC#11とPython3.9です。

Amicable.cs

long sumDivisor(long x)
{
    long sum = 1;

    for (long i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            if (i * i == x)
            {
                sum += i;
            }
            else
            {
                sum += i;
                sum += x / i;
            }
        }
    }

    return sum;
}

long n = long.Parse(Console.ReadLine());

for (long i = 2; i <= n; i++)
{
    long j = sumDivisor(i);

    if (sumDivisor(j) == i && i < j)
    {
        Console.Write(i);
        Console.Write(", ");
        Console.WriteLine(j);
    }
}

Amicable.py

import math

def sum_divisor(x):
    sum = 1
    
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            if i * i == x:
                sum += i
            else:
                sum += i
                sum += x / i
                
    return int(sum)

n = int(input())

for i in range(2, n + 1):
    j = sum_divisor(i)
    
    if sum_divisor(j) == i and i < j:
        print(str(i) + ', ' + str(j))

参考