1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

高度合成数を列挙してみる

Posted at

#高度合成数とは
Wikiでは、

自然数で、それ未満のどの自然数よりも約数の個数が多いもの

となっている。
直感的にはわかりにくいので、簡単に言ってしまうと
割れる数が多い割に小さい数
といったところだろうか。
12,24,36といった数がそれに該当する。
聞き馴染みがある数だと思われる。

わかりやすく解説してくださっているサイトもいくつかあるので、
詳しくはそちらへ(´∀`)

#本題
とりあえず定義どおりに素直に組んでみたので、いい感じの効率化を思いつけば追記します。

HighlyCompositeNumber.cs
//EnumerableExtention.HighlyCompositeNumber(10000);
//result:2,4,12,24,36,60,120,180,240,360,720,840,1260,1680,2520,5040,7560
public static IEnumerable<int> HighlyCompositeNumber(int limit)
{
	var maxDivisorCount = 0;
	for (int i = 2; i < limit; i++)
	{
		var divisorCount = CountDivisor(i);
		if (maxDivisorCount < divisorCount)
		{
			yield return i;
			maxDivisorCount = divisorCount;
		}
	}
}

private static int CountDivisor(int value)
{
	if (value <= 1) { return 1; }
	var divisors = new List<int>();
	for (int i = 1; i < value; i++)
	{
		if (value % i != 0) { continue; }

		var f = value / i;
		if (divisors.Contains(f)) { break; }
		divisors.Add(i);
		if (i == f) { break; }
	}
	return divisors.Count;
}
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?