Zenn
🙆

【C#アルゴリズム】素数の判定

2024/11/24に公開
C#
アルゴリズム
素数
tech

はじめに

paiza　、アルゴリズムの本で素数の判定アルゴリズムについて学んだのでまとめました。以下に、試し割り法、エラトステネスの篩、フェルマーテストについての特徴と、それぞれのC#コード例を説明します。

1. 試し割り法

特徴

  • 簡単さ: 素数判定の基本的な方法。
  • 効率: 入力値が大きくなると効率が悪くなりやすい。
  • 使いどころ: 比較的小さな数を判定する場合に適している。

アルゴリズム

  1. 数 n が 2 未満なら素数ではない。
  2. n を 2 から \sqrt{n} 以下の整数で割り、割り切れるかを確認。
  3. 割り切れた場合、素数ではない。

C# 実装例

private static bool IsPrime(long n)
{
    if (n == 1)
    {
        return false;
    }
    for (long i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
    return true;
}

2. エラトステネスの篩

特徴

  • 効率: n 以下のすべての素数を求めるのに効率的。
  • 使いどころ: 一度に多くの素数を列挙する場合に適している。
  • メモリ使用量: 大量の数値を扱う場合にはメモリを多く消費する。

アルゴリズム

  1. 配列 isPrime を用意し、サイズを N+1（インデックスが 0 から N まで使えるように）とする。すべての要素を true に初期化する。ただし、isPrime[0] と isPrime[1] は最初から false に設定する（0 と 1 は素数ではないため）。

  2. 整数 i を 2 から N まで順番に調べる。次の手順を実行する：

    • isPrime[i] が true である場合、i は素数と判定される。その後、i の倍数である 2 \times i, 3 \times i, 4 \times i, \ldots を順に調べ、それらに対応する isPrime[j]（ただし j = k \times i かつ j \leq N）を false にする。

C# 実装例

private static bool[] Eratosthenes(int n)
{
    bool[] isPrimes = Enumerable.Repeat(true, n + 1).ToArray();
    isPrimes[0] = isPrimes[1] = false;
    for (int i = 2; i <= n; i++)
    {
        if (isPrimes[i])
        {
            for (long j = i * 2; j <= n; j += i)
            {
                isPrimes[j] = false;
            }
        }
    }
    return isPrimes;
}

3. フェルマーテスト

特徴

  • 効率: 確率的な判定法として非常に高速。
  • リスク: 高確率なだけなので素数でないものが素数と判定されることがある。
  • 使いどころ: 大きな数の素数性を迅速にチェックする場合。

アルゴリズム

  1. a を 2 から N-1 までの整数の中からランダムに選ぶ。
  2. N が a で割り切れる場合、N は素数ではないと判定する。
  3. a^{N-1} を N で割った余りが 1 ならば、N は素数であると判定し、1 でない場合は素数ではないと判定する。

C# 実装例

private static bool FermatTest(int n)
{
    int a = 2;
    if (n % a == 0)
    {
        return false;
    }
    int fermat = 1;
    for (int i = 0; i < n - 1; i++)
    {
        fermat *= a;
        fermat %= n;
    }
    return fermat == 1 ? true : false;
}

まとめ

方法 特徴 長所 短所
試し割り法 単純な方法 実装が簡単 大きな数には非効率
エラトステネスの篩 複数の素数を効率的に求める方法 一度に大量の素数を計算可能 メモリ使用量が多い
フェルマーテスト 確率的な高速判定 非常に大きな数にも対応可能 誤判定が起こる可能性がある

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/3YtOnpz

Discussion