2016.02.02

数学

素数リスト作成

指定した数値以下の全ての素数を表示するプログラムの解説をします。

ここで紹介するのは、配列を使って自分自身の数以外で割り切れない数値を見つけるアルゴリズムです。

整数Nまでの素数を表示する場合について説明します。

まず、(N+1)個のint型配列を用意し、その値を全て0にします。

次に、2で割り切れる配列番号のうち2以上のもの(2,4,6...)の配列値に1を足します。

さらに、3で割り切れる配列番号のうち2以上のもの(3,6,9...)の配列値に1を足します。

これと同じ処理をNまで繰り返します。この処理が終わった時の配列の値が1である配列番号が素数となります。

配列の値が1の配列番号は、自分自身の番号だけで1を足されていて、言い換えれば自分自身の番号以外で割り切れないこと意味しています。

Javaソースコード

以下が、そのJavaソースコードです。

PrimeNumber2.java

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
public class PrimeNumber2 {
	// メイン
	public static void main( String[] args ) {
		// 変数の宣言
		int number;	// 上限値

		// 入力した引数が1つ以上かを調べる
		if ( 1 > args.length ) {
			// 入力した引数が1つ未満の場合、使用方法を表示する
			System.out.println( "PrimeNumber2 [上限値]" );
			return;
		}


		// 引数をint型に変換しnumberに代入
		try {
			number = Integer.parseInt( args[ 0 ] );
		}
		catch( NumberFormatException ne )
		{
			// args[0]が数字ではない
			System.out.println( "[上限値]の取得に失敗しました" );
			return;
		}

		// 上限値が1の場合、終了
		if ( 1 >= number ) {
			System.out.println( "表示する素数がありません" );
			return;
		}

		// 上限値+1のint型配列を宣言
		int[] count = new int[ number + 1 ];
		
		// 配列に0を格納
		for ( int i = 0; i <= number; ++ i ) count[ i ] = 0;

		// iで割り切れる配列番号に1を足していく
		for ( int i = 2; i <= number; ++ i ) {
			int pos = i;
			while ( pos <= number ) {
				++ count[ pos ];
				pos += i;
			}
		}

		// 配列の値が1の番号を表示
		for ( int i = 2; i <= number; ++ i ) {
			if ( 1 == count[ i ] ) System.out.println( i );
		}
	}
}

コンパイル ソースコードが「ANSI」の場合

C:\talavax\javasample>javac -encoding sjis PrimeNumber2.java

コンパイル ソースコードが「UTF-8」の場合

C:\talavax\javasample>javac PrimeNumber2.java

実行

C:\talavax\javasample>java PrimeNumber2 50

1つ目の引数に50を渡して、50以下の素数を表示しています。

出力結果

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47

ここからは、素数のリストを表示するプログラムの説明をします。

001
public class PrimeNumber2 {

クラス名を、PrimeNumber2としています。

002
003
	// メイン
	public static void main( String[] args ) {

このmainメソッドからプログラムを実行します。

004
005
		// 変数の宣言
		int number;	// 上限値

このプログラムで使う変数を宣言しています。numberは表示する素数の上限値です。

007
008
009
010
011
012
		// 入力した引数が1つ以上かを調べる
		if ( 1 > args.length ) {
			// 入力した引数が1つ未満の場合、使用方法を表示する
			System.out.println( "PrimeNumber2 [上限値]" );
			return;
		}

1つ以上の引数が与えられたかをチェックし、1つ未満の場合に、使い方のメッセージを表示し、returnによってmainメソッドを抜けています。

015
016
017
018
019
020
021
022
023
024
		// 引数をint型に変換しnumberに代入
		try {
			number = Integer.parseInt( args[ 0 ] );
		}
		catch( NumberFormatException ne )
		{
			// args[0]が数字ではない
			System.out.println( "[上限値]の取得に失敗しました" );
			return;
		}

1つ目の引数をnumberに格納しています。与えられた引数が数値でない場合、returnによってmainメソッドを抜けています。

026
027
028
029
030
		// 上限値が1の場合、終了
		if ( 1 >= number ) {
			System.out.println( "表示する素数がありません" );
			return;
		}

表示する素数の上限値を格納した変数numberが1以下の場合、「表示する素数がありません」と表示してプログラムを終了しています。

032
033
		// 上限値+1のint型配列を宣言
		int[] count = new int[ number + 1 ];

(number+1)個のint型配列を定義しています。ここで紹介する方法は、numberの数が大きくなればメモリ消費量が多くなります。

035
036
		// 配列に0を格納
		for ( int i = 0; i <= number; ++ i ) count[ i ] = 0;

全ての配列の値を0にしています。以下の例ではnumber=10です。

素数リスト 配列初期化
038
039
040
041
042
043
044
045
		// iで割り切れる配列番号に1を足していく
		for ( int i = 2; i <= number; ++ i ) {
			int pos = i;
			while ( pos <= number ) {
				++ count[ pos ];
				pos += i;
			}
		}

for文でiを2からnumberまで1つずつ変化させ、while文でiの倍数の配列番号の値に1を足していきます。i=2でnumber=10の場合、2と4とと6と8と10の配列に1を足します。

素数リスト 2の倍数の配列に1を足す

同様に3からnumber=10まで処理を実行すると、配列の値は以下のように変化していきます。

素数リスト 3の倍数の配列に1を足す 素数リスト 4の倍数の配列に1を足す 素数リスト 5の倍数の配列に1を足す 素数リスト 6の倍数の配列に1を足す 素数リスト 7の倍数の配列に1を足す 素数リスト 8の倍数の配列に1を足す 素数リスト 9の倍数の配列に1を足す 素数リスト 10の倍数の配列に1を足す
047
048
049
050
		// 配列の値が1の番号を表示
		for ( int i = 2; i <= number; ++ i ) {
			if ( 1 == count[ i ] ) System.out.println( i );
		}

最後に、配列の値が1の配列番号が表示する素数になります。これは、その配列番号が自分自身の番号以外で割り切れなかったことを意味しています。

素数リスト 素数の位置

number=10の場合、表示される素数は、2と3と5と7です。

次のコンテンツ

指定した個数の素数の出力するJavaソースコードを紹介しています。

2023.01.03

前のコンテンツ

素数を判定するプログラムを作成してみませんか?興味のある方は、ご覧ください。

2016.02.01

関連コンテンツ

数学に関係するJavaのメソッドやソースコードなどを紹介しています。

2022.10.25

同じ型の変数(データ)を複数個まとめて管理するデータの持ちかたがあります。これが配列です。くわしくは、記事をご覧ください。

2016.01.14

基本的な計算である足し算(加法)/引き算(減法)/掛け算(乗法)/割り算(除法)を行うプログラム作成。

2020.03.23

割り算で「割り切れる」、「割り切れない」ってどういうこと?

条件式を判断して処理を分岐する方法を詳しく説明しています。

2023.03.20

変数やクラスに格納されている値をコンソール出力する方法は?

2020.03.23

メソッドを抜けるときに使用するreturn文について説明しています。

2020.03.20

処理を繰り返すために使用するwhile文について解説しています。

2016.01.26

繰り返し処理の作り方を解説しています。

2016.03.02

プログラムの最初に実行されるメソッドは?

2022.12.13

プログラミングで使う変数って何?

2020.03.23

Javaのプログラムを書いてみませんか?プログラムの書き方をくわしく説明しています。

2020.03.23

「Javaソースコード」から実行可能な「オブジェクトコード」に変換する方法をくわしく説明しています。

2020.03.23

指定した個数の素数の出力するJavaソースコードを紹介しています。

2023.01.03

素数を判定するプログラムを作成してみませんか?興味のある方は、ご覧ください。

2016.02.01

自然数と整数って何が違う?

2020.03.23

プログラミング言語とは?種類や特徴について説明しています。

2022.08.03

メソッドの定義方法を詳しく解説しています。Javaのサンプルソースコードを使った説明もあります。

2020.03.23

Javaプログラムの構成について解説しています。詳しくは、こちらをご覧ください。

2020.03.23

for文で変数名iがよく使われる理由について説明しています。興味のある方は是非。

2022.08.29

Java仮想マシン内のメモリ容量を取得するプログラムを作ってみませんか?

2016.12.14

処理を繰り返すために使用するfor文について解説しています。

2020.03.23

広告