Javaプログラミング学習サイト ゆるゆるプログラミング

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ソースコードです。

PrimeNumber2.java ← クリックしてダウンロードページに移動
001:    public class PrimeNumber2 {
002:    	// メイン
003:    	public static void main( String[] args ) {
004:    		// 変数の宣言
005:    		int number;	// 上限値
006:    
007:    		// 入力した引数が1つ以上かを調べる
008:    		if ( 1 > args.length ) {
009:    			// 入力した引数が1つ未満の場合、使用方法を表示する
010:    			System.out.println( "PrimeNumber2 [上限値]" );
011:    			return;
012:    		}
013:    
014:    
015:    		// 引数をint型に変換しnumberに代入
016:    		try {
017:    			number = Integer.parseInt( args[ 0 ] );
018:    		}
019:    		catch( NumberFormatException ne )
020:    		{
021:    			// args[0]が数字ではない
022:    			System.out.println( "[上限値]の取得に失敗しました" );
023:    			return;
024:    		}
025:    
026:    		// 上限値が1の場合、終了
027:    		if ( 1 >= number ) {
028:    			System.out.println( "表示する素数がありません" );
029:    			return;
030:    		}
031:    
032:    		// 上限値+1のint型配列を宣言
033:    		int[] count = new int[ number + 1 ];
034:    		
035:    		// 配列に0を格納
036:    		for ( int i = 0; i <= number; ++ i ) count[ i ] = 0;
037:    
038:    		// iで割り切れる配列番号に1を足していく
039:    		for ( int i = 2; i <= number; ++ i ) {
040:    			int pos = i;
041:    			while ( pos <= number ) {
042:    				++ count[ pos ];
043:    				pos += i;
044:    			}
045:    		}
046:    
047:    		// 配列の値が1の番号を表示
048:    		for ( int i = 2; i <= number; ++ i ) {
049:    			if ( 1 == count[ i ] ) System.out.println( i );
050:    		}
051:    	}
052:    }

PrimeNumber2を実行

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

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

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

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

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

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

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

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

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

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

素数リスト 配列初期化

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

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:    		// 配列の値が1の番号を表示
048:    		for ( int i = 2; i <= number; ++ i ) {
049:    			if ( 1 == count[ i ] ) System.out.println( i );
050:    		}

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

素数リスト 素数の位置

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

■関連コンテンツ

素数判定 素数の判定方法を解説
Javaの配列 同じ型の変数をまとめた配列について解説
繰り返し処理に使用するfor文について解説-画像

for文

繰り返し処理に使用するfor文をJavaのソースコードを使って説明しています。

四則演算(足し算/引き算/掛け算/割り算)について-画像

計算結果の表示

足し算(加法)/引き算(減法)/掛け算(乗法)/割り算(除法)の使い方を説明

■新着情報

2021.06.23 配列の初期値 配列の生成直後の値は?
2021.06.18 変数の初期値 変数に値を代入しないで計算

■広告

 

 

 

 

 

スッキリわかるJava入門第3版 [ 中山清喬 ]

価格:2,860円
(2021/6/18 14:32時点)
感想(6件)

 

 

 

Topへ