素数かどうか判定するメソッド

作成日：2009/10/17　分類：C#

シンプルな実装方法

解説

　下記のソースコードのIsPrimeメソッドを呼び出すと、引数に指定された値が素数かどうか判定します。

　IsPrimeメソッド内のループ（※1）では、nをまず2で割り、2で割った余りが0であれば素数でないと判断します。このとき、falseを返してメソッドを抜けます。同様に、3で割り算、4で割り算とくり返し、nより小さい値では割りきれないことが分かると、trueを返します。

ソースコード全体（Program.cs）

using System;

namespace PrimeListup
{
  class Program
  {
    static void Main(string[] args)
    {
      for(int i=0; i<20; i++)
      {
        Console.Write(i);
        if(IsPrime(i))
          Console.WriteLine(" は素数です。");
        else
          Console.WriteLine(" は素数ではありません。");
      }
    }

    static bool IsPrime(int n)
    {
      if(n<2) return false;
      if(n==2) return true;

      for(int i=2; i<n; i++)     // ※1
      {
        if(n%i==0) return false;
      }
      return true;
    }
  }
}

実行結果

0 は素数ではありません。
1 は素数ではありません。
2 は素数です。
3 は素数です。
4 は素数ではありません。
5 は素数です。
6 は素数ではありません。
7 は素数です。
8 は素数ではありません。
9 は素数ではありません。
10 は素数ではありません。
11 は素数です。
12 は素数ではありません。
13 は素数です。
14 は素数ではありません。
15 は素数ではありません。
16 は素数ではありません。
17 は素数です。
18 は素数ではありません。
19 は素数です。

発展的な内容

　上記のメソッドでは、nが2でも3でもで割り切れなかった場合、次に4で割り切れるかどうか計算します。しかし、2で割り切れない値を4で割り切れるはずはありません。そこで、※1の部分を書き換え、偶数で割るのを省略すると、無駄な処理をちょっとだけ省くことができます。

    static bool IsPrime(int n)
    {
      if(n<2) return false;
      if(n==2) return true;

      for(int i=3; i<n; i+=2)        // ※2
      {
        if(n%i==0) return false;     // ※3
      }
      return true;
    }

　※1の行は書き換えて※2にしました。2以上のすべての整数で余りを求めるのではなく、3以上の奇数で割った余りを求めるようになりました。

　しかし、2で割った余りを計算する部分がなくなってしまいました。そのため4や8が素数だと判定してしまいます。

　そこで、次のように書き換えます。※4の行で、2で割った余りを計算するので、2以外の偶数は素数でないと判定できるようになりました。

    static bool IsPrime(int n)
    {
      if(n<2) return false;
      if(n==2) return true;
      if(n%2==0) return false;       // ※4

      for(int i=3; i<n; i+=2)
      {
        if(n%i==0) return false;
      }
      return true;
    }