【C#】素数判定のプログラムを書いてみる

はじめに

今回は素数判定のプログラムを書いてみようという記事になります！

素数とは一とその数自身との外には約数がない1より大きい正の整数のことです。

例えば7は素数ですが、8は素数ではありません。

では早速みていきましょう。

はじめに
素数判定
改良してみる
さいごに

素数判定

基本的な考え方は2から入力された数-1までで割り切れるかを調べて、割り切れなければ素数となります。

/// <summary>
/// 素数判定
/// </summary>
public static bool IsPrime(long x)
{
    if (x < 2) return false;

    for (long i = 2; i < x; i++)
    {
        if (x % i == 0) return false;
    }

    return true;
}

改良してみる

素数判定をする際に、その数の平方根までに約数を持つかどうかを調べるだけで済むということが証明されています。
エラトステネスの篩で調べる素数判定の上限と平方根の関係性 - Szarny.io

これを用いることで繰り返しの数を減らすことができます。

加えて2を除く偶数は必ず素数ではないので、あらかじめ除いておくことでさらに繰り返し回数を減らすこともできます。

またこの理論でいけば3,5,7,...とあらかじめ除いても良いということになりますが、劇的に速度に変化はないようです。

/// <summary>
/// 素数判定
/// </summary>
public static bool IsPrime(long x)
{
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;

    double sqrtX = Math.Sqrt(x);
    for (long i = 3; i < sqrtX; i += 2)
    {
        if (x % i == 0) return false;
    }

    return true;
}