#高度合成数とは
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;
}