Java 素数の求め方

素数って何だっけ？

だいたい競プロの問題に挑戦すると、あー学生の頃に習ったことあるけど何だったか全然思い出せねーってなります。

素数とは、Wikipediaによると

素数（そすう、英: prime number）とは、1より大きい自然数で、正の約数が1と自分自身のみであるもののことである。正の約数の個数が2である自然数と言い換えることもできる。

だそうです。
つまり、1より大きい整数で、1と自分自身でしか割り切れない数のことですね。

素数判断のプログラム

import java.util.Scanner;

public class PrimeNumber {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int target = sc.nextInt();

    if (target < 2) {
      System.out.println(target + "は素数ではありません。");
      return;
    }

    for (int i = 2; i < target; i++) {
      if (target % i == 0) {
        System.out.println(target + "は素数ではありません。");
        return;
      }
    }

    System.out.println(target + "は素数です。");
  }
}

解説

1より大きい整数

    if (target < 2) {
      System.out.println(target + "は素数ではありません。");
      return;
    }

ここでは、素数ので意義である1より大きい整数かどうかをチェックしています。
2より小さければ素数ではないとわかるので、出力してさっさと処理を終了させます。

1と自分自身でしか割り切れない数

肝になるのはやっぱりこの部分です。

    for (int i = 2; i < target; i++) {
      if (target % i == 0) {
        System.out.println(target + "は素数ではありません。");
        return;
      }
    }

    System.out.println(target + "は素数です。");

for文で、2からtarget-1までの数で1つずつ割っていって、割り切れるかどうかをチェックしていきます。
ひとつでも割り切れる数が存在する場合、その数は素数ではないので、出力してreturnで処理を終了させます。

割り切れる数がない場合、targetは素数ということになります。

高速化

素数かどうか調べるための単純な方法として、1と対象数以外の全ての数で割っていく上記の方法を行いました.
しかし、この方法だと調べる対象数が大きいほど、計算に時間がかかってしまいます。

そこで、コメントでいただいたように、素数かどうかは平方根以下の値のみのチェックすれば判定できるようです。

なぜ平方根まででいいのか

素数とは、1と自分自身でしか割り切れない数のことでしたが、それ以外の数を合成数と言います。
つまり、合成数とは、1でも素数でもない数のことです。
言い換えると、合成数は1と自分自身以外に最低でも1つの約数をもつということになります。

また、合成数は√n以下の約数をもつという性質を持っています。

合成数は√n以下の約数をもつ

なぜ合成数は√n以下の約数をもつと言えるのでしょうか？

まず合成数nは、1でない自然数a,bが存在しているためｎ=abと表せます。
もし、nが√ｎ以下の約数を持たないとすると、√ｎ<a,√ｎ<bとなります。
√ｎは0より大きいため、√ｎ<a,√ｎ<bの場合（nが√ｎ以下の約数を持たない場合）、√ｎ√ｎ(=n)はabより小さいということになってしまい、ｎ=abに反します。
そのため、ｎは√ｎ以下の約数を持つと言えるのです。

つまり、nが合成数なら、√x以下の約数を持つということは、√x以下に約数があるかどうがをチェックすれば、
その数が素数かどうか判定できるということになります！

改・素数判断のプログラム

import java.util.Scanner;

public class PrimeNumber {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int target = sc.nextInt();

    if (target < 2) {
      System.out.println(target + "は素数ではありません。");
      return;
    }
    if (target % 2 == 0) { // 偶数は先にリターン
      System.out.println(target + "は素数ではありません。");
      return;
    }

    for (int i = 3; i <= Math.sqrt(target); i+=2) {
      if (target % i == 0) {
        System.out.println(target + "は素数ではありません。");
        return;
      }
    }

    System.out.println(target + "は素数です。");
  }
}