【C#】約数を列挙するプログラムを実装してみる

はじめに

今回は約数を列挙するプログラムを実装してみる記事になります！

一応約数とはなにかというとこんな感じ。

数 a ≠ 0 が N の約数であるとは、「ある整数 b をとると N = ab が成立することである」であるが、条件「a ≠ 0」を外すこともある。

約数 - Wikipedia

例えば6の約数は1, 2, 3, 6となります。

早速コードを見ていきましょう。

一番シンプルなもの

まずは一番シンプルだと思うコードはこちら。

public static IEnumerable<long> GetDivisors(long num)
{
    if (num < 1) yield break;

    for (long i = 1; i <= num; i++)
    {
        if (num % i == 0) yield return i;
    }
}

1から入力された数までにおいて「割り切れるか」調べ、割り切れたら列挙をします。

使う時はこんな感じ。

static void Main(string[] args)
{
    long num = 124;
    foreach (var item in GetDivisors(num))
    {
        Console.WriteLine(item);　　// 1 2 4 31 62 124
    }
}

改良したもの

しかし先程のは全部を調べているので比較的遅く、計算量はになってしまいます。

ここで約数のある性質を用いて高速化を測ります。

「a が N の約数ならば、も N の約数である」ことを使うと、半分程度の労力で済む。

約数 - Wikipedia

これを利用することで計算量にまで抑えることができます。

public static IEnumerable<long> GetDivisors(long num)
{
    if (num < 1) yield break;

    for (long i = 1; i * i <= num; i++)
    {
        if (num % i == 0)
        {
            yield return i;
            if (i * i != num) yield return (num / i);
        }
    }
}

1
124
2
62
4
31

ただしこちらの方法だと出力される順番がソートされていないことに注意してください。

もしソートしたい場合はLINQを使うと良いでしょう。

var sortedDivisors = GetDivisors(num).OrderBy(t => t);

追記) 実装するとき 前，後ろ，前，後ろのように追加していけばLINQを使わずとも順番に並んでいきます。

比較してみる

とても大きい値を使って、パフォーマンスを確かめてみました。

n = の約数を全部調べてみたときの処理時間はこちら。

シンプルな奴	改良版	改良版(LINQによるソート有り)
9757ms	0ms	5ms

計算量的にこうなるのはわかっていましたが、実際に数字として表すとかなりの差ですよね。

たとえソートをしたい場合でも改良版を使った方がよいでしょう。

さいごに

今回は約数を列挙するプログラムを作成しましたが、アルゴリズムの大切さを知れた実装でもありました。

LINQは遅いみたいな話も聞きますが、それ以前にもっと気を付けれければならない箇所があるのかもしれませんね。

是非うまく活用してみてください。

ではまた。