スミス数を求めるプログラム

スミス数を求めるプログラムをC++で実装します。実行環境はVisual Studio Community 2022バージョン17.10.1とC++20です。

スミス数の定義

合成数で、その素因数の各位の数字の和の合計が元の数字の各位の数字の和に等しい数をスミス数と呼びます。
例えば648の各位の数字の和は$6 + 4 + 8 = 18$より18です。
一方、648を素因数分解すると$648 = 2^{3} + 3^{4}$なので、648の素因数の各位の数字の和の合計は$2×3+3×4 = 18$より18となり、元の数字の各位の数字の和に等しいので、648はスミス数に該当します。

プログラム

スミス数自体は無限に存在しますが、ここでは正の整数Nまでのスミス数を求めて列挙するプログラムを以下に書きます。

Smith.cpp

#include <iostream>
#include <vector>

//素数判定のための関数
bool isPrime(long long x)
{
	for (long long i = 2; i * i <= x; i++)
	{
		if (x % i == 0)
		{
			return false;
		}
	}

	return true;
}

//各位の和を計算する関数
long long digit_sum(long long n)
{
	long long sum = 0;

	while (n > 0)
	{
		sum += n % 10; //1の位の数字を求めて合計に加算
		n /= 10; //10で割って右に1桁シフトさせる
	}

	return sum;
}

//スミス数判定の関数
bool isSmith(long long n)
{
	std::vector<long long> prime_factor; //分解した素因数を格納するための配列
	long long m = n;

    //while文の中で素因数分解を実行
	while (m > 1)
	{
		for (long long i = 2; i <= m; i++)
		{
			if (m % i == 0)
			{
				prime_factor.emplace_back(i);
				m /= i;
				break;
			}
		}
	}

	long long prime_sum = 0; //素因数の各位の数字の和の合計を入れるための変数

    //素因数の各位の数字の和を加算していく
	for (auto x : prime_factor)
	{
		prime_sum += digit_sum(x);
	}

    //元の数字の各位の和と素因数の各位の和の合計を比較
	if (digit_sum(n) == prime_sum)
	{
		return true;
	}
	else
	{
		return false;
	}
}

int main()
{
	long long N; //スミス数を計算する上限値
	N = 1000;
	
	for (int i = 2; i <= N; i++)
	{
		if (isSmith(i) == true && isPrime(i) == false)
		{
			std::cout << i << std::endl;
		}
	}
}

main関数の最後で素数判定を忘れないようにしましょう。スミス数は合成数であることが定義されています。素数が条件を満たすのは当然ですが、定義に従い素数は除外します。isSmith関数がtrue、isPrime関数がfalse、この2つが同時に成立する数字のみを出力します。

出力結果

4
22
27
58
85
94
121
166
202
265
274
319
346
355
378
382
391
438
454
483
517
526
535
562
576
588
627
634
636
645
648
654
663
666
690
706
728
729
762
778
825
852
861
895
913
915
922
958
985

参考