素数判定をStream APIで実装した

こんにちは。今回はStream APIの練習として、素数判定の実装を考えてみました。ただし、素数判定のアルゴリズムは素数の定義を用いた基本的なものです。また、アルゴリズムの速さは考慮しません。

最初にStream APIを使わないサンプルを作成しました。次にStream APIを使ったサンプルを作成しました。最後に、約数を全て出力することを考えました。

1 素数の定義について
2 for文を使った実装
3 Stream APIを使った実装
4 約数を保持したい場合

素数の定義について

２以上の自然数Nが素数とは、Nが1とN以外に約数を持たないときに言います。ここで、約数とは、自然数Nを割り切る自然数のことです。（今回の記事では自然数のみを考えてます。）

たとえば、２、３、５、７は素数です。

５が素数かどうか調べるのには、１から５までの自然数それぞれについて、５を割って余りが１以上か計算することでわかります。

５を割る数	割り切れるか
１	Yes.
２	No.
３	No.
４	No.
５	Yes.

上記のように、５の約数は１とそれ自身だけです。なので、５は素数です。

４や６は素数ではありません。このような数は合成数と呼ばれます。

for文を使った実装

最初にfor文を使った実装を考えました。自然数nを引数にして、素数であるか判定するメソッドを作りました。

ソース

public class Test001 {

	public static void main(String[] args) {
		Test001 t = new Test001();

		System.out.println("方法１");
		for (int i = 1; i < 20; i++) {
			System.out.println(i + ": " + t.primarityOf(i));
		}
	}

	public boolean primarityOf(int n) {
		//(1)
		if (n < 2) {
			return false;
		}

		// (2)
		int cnt = 0;
		for (int i = 2; i < n; i++) {
			if (n % i == 0) {
				cnt ++;
			}
		}

		// (3)
		return cnt == 0;
	}

}

結果

方法１
1: false
2: true
3: true
4: false
5: true
6: false
7: true
8: false
9: false
10: false
11: true
12: false
13: true
14: false
15: false
16: false
17: true
18: false
19: true

上記サンプルのprimarityOf()メソッドは引数が素数の場合trueを返却するメソッドです。

(1)では便宜上、nが2より小さい場合は、falseを返却するようにしました。

(2)では2からn-1までの自然数のうち、約数であるものをカウントしています。1とn自身は常に約数であるので、カウント対象にしていません。

変数cntはカウント用の変数です。for文では繰り返し用変数iが2からn-1までで処理を繰り返しています。nをiで割った余りが0の場合、iはnの約数です。if文によって、その場合だけcntを1加算しています。

(3)では条件式をreturn文に指定しています。このように記述すると、その条件式の結果がメソッドの返却値です。nが約数を1とそれ自身以外持たない場合、cntが0です。なので、その場合にtrueがリターンされるようにしています。

Stream APIを使った実装

上述のサンプル（for文を使った素数の判定処理）をStream APIを使って書き直しました。

ソース

import java.util.stream.IntStream;

public class Test002 {

	public static void main(String[] args) {
		Test002 t = new Test002();

		System.out.println("方法2");
		for (int i = 1; i < 20; i++) {
			System.out.println(i + ": " + t.primarityOf(i));
		}
	}

	public boolean primarityOf(int n) {
		//(1)
		if (n < 2) {
			return false;
		}

		// (2)
		long cnt = IntStream.range(2, n)
				.filter(i -> n % i == 0)
				.count();

		// (3)
		return cnt == 0;
	}
}

結果

方法2
1: false
2: true
3: true
4: false
5: true
6: false
7: true
8: false
9: false
10: false
11: true
12: false
13: true
14: false
15: false
16: false
17: true
18: false
19: true

(1)は変更箇所がありません。

(2)でStream APIを使っています。

IntStreamのrange()メソッドは以下のように定義されたメソッドです。

static IntStream range(int startInclusive, int endExclusive)

このメソッドでは、startInclusive以上、endExclusive未満の自然数で構成されたIntStreamを取得できます。

例えば、2と10を指定した場合、2から9までの自然数で構成されたIntStreamが返却されます。

range()の例

IntStream stream = IntStream.range(2, 10);
System.out.println(Arrays.toString(stream.toArray()));

結果

[2, 3, 4, 5, 6, 7, 8, 9]

そのあとに呼び出しているfilter()メソッドは中間操作のメソッドです。ラムダ式を引数に指定することができます。各値iに対して、「nをiで割った余りが0であるか」という条件式を返却するように指定しています。filter()メソッドは、IntStreamの各要素のうち、ラムダ式の結果がtrueである要素のみを抽出してくれます。なお、IntStreamに対して、filter()メソッドを呼び出しているので、抽出結果もIntStreamです。

以下は具体的な値の場合の例です。

filter()の例

IntStream stream = IntStream.range(2, 10)
		.filter(i -> 12 % i == 0);
System.out.println(Arrays.toString(stream.toArray()));

結果

[2, 3, 4, 6]

その後に呼び出しているのは、count()メソッドです。IntStreamの要素の個数を取得できます。このメソッドは終端操作の一つです。上記のように記述することで、1とn自身以外の約数の個数が変数cntに格納されます。

(3)でcntが0の時にtrueを返却しています。

上記のようにfor文をStream APIに書き換えることができました。

約数を保持したい場合

約数を保持したい場合はどうすればよいか、考えました。約数を保持するクラスを作るのが一番簡単だと思いました。

例えば、以下のように実装することができました。

約数を保持するためのクラス

import java.util.stream.IntStream;

/**
 * 自然数と約数を格納するクラス
 */
public class MyNumber {
	/**
	 *　自然数
	 */
	private int num;

	/**
	 * 約数
	 */
	private int[] divisor;

	public MyNumber(int num) {
		this.num = num;

		/* 約数を求める処理 */
		divisor = IntStream.rangeClosed(1, num)
				.filter(i -> num % i == 0)
				.toArray();
	}

	public int getNum() {
		return num;
	}

	public int[] getDivisor() {
		return divisor;
	}

}

約数を出力

import java.util.Arrays;

public class Test003 {

	public static void main(String[] args) {
		System.out.println("約数を表示");
		for (int i = 1; i < 20; i++) {
			MyNumber myNumber = new MyNumber(i);
			int[] divisor = myNumber.getDivisor();

			System.out.println("------------------------------");
			System.out.println(i);
			System.out.println("約数" + Arrays.toString(divisor));
			System.out.println("素数判定：" + (i >= 2 && divisor.length == 2));
		}

	}

}

結果

約数を表示
------------------------------
1
約数[1]
素数判定：false
------------------------------
2
約数[1, 2]
素数判定：true
------------------------------
3
約数[1, 3]
素数判定：true
------------------------------
4
約数[1, 2, 4]
素数判定：false
------------------------------
5
約数[1, 5]
素数判定：true
------------------------------
6
約数[1, 2, 3, 6]
素数判定：false
------------------------------
7
約数[1, 7]
素数判定：true
------------------------------
8
約数[1, 2, 4, 8]
素数判定：false
------------------------------
9
約数[1, 3, 9]
素数判定：false
------------------------------
10
約数[1, 2, 5, 10]
素数判定：false
------------------------------
11
約数[1, 11]
素数判定：true
------------------------------
12
約数[1, 2, 3, 4, 6, 12]
素数判定：false
------------------------------
13
約数[1, 13]
素数判定：true
------------------------------
14
約数[1, 2, 7, 14]
素数判定：false
------------------------------
15
約数[1, 3, 5, 15]
素数判定：false
------------------------------
16
約数[1, 2, 4, 8, 16]
素数判定：false
------------------------------
17
約数[1, 17]
素数判定：true
------------------------------
18
約数[1, 2, 3, 6, 9, 18]
素数判定：false
------------------------------
19
約数[1, 19]
素数判定：true

MyNumberのフィールドは判定対象の自然数numと約数の配列divisorです。

コンストラクタでそれぞれのフィールドに値を格納しています。判定対象となる自然数を引数にしているので、フィールドnumには引数を格納しています。その後、Stream APIで約数を抽出した後、toArray()メソッドで配列を取得しています。これをフィールドdivisorに格納しています。このクラスを使うことで約数を出力することができました。

以上、参考になれば幸いです。