素数判定 - 【ゆるゆるプログラミング】

2016/02/01 公開

・素数判定

素数とは、１と自分自身でだけで割り切れる２以上の数です。（１は素数ではありません）

ここで説明する方法は、素数と判定する整数Nを２から順番に√N（Nの平方根）までの数で割っていき、割り切れたら素数ではない、割り切れなかったたら素数と判定するものです。

割り切れるかの判定を√Nで打ち切るかの理由は、Nを√Nより大きい数値で割った商は√N以下になり、√Nより大きい数値で割り切れるなら、√N以下の商で既に割り切れているためです。

例として素数である１１で説明します。この場合√１１の整数部は３です。２から３の値で１１を割っていき、割り切れなければ素数としています。ここで、なぜ３（＝√Nの整数部）より大きい整数で割る必要がないかを考えます。１１を４で割った商は２で余り３です。１１を５で割った商は２で余り１です。１１を６で割った商は１で余り５です。このように商が３より大きい値になりません。よって、仮に４と５で割り切れるなら、２か３でも割り切れていたはずです。よって、√Nを割る数の上限にしています。

判定時間を短くするために上限を√Nとしていますが、整数Nを２からN-1までの値で素数判定を行ってもよいです。判定結果は同じですが、判定時間が長くなります。

以下が、素数判定のJava ソースコードです。

PrimeNumber1.java　←　クリックしてダウンロードページに移動

001:    public class PrimeNumber1 {
002:    	// 素数判定メソッド
003:    	private static boolean isPrimeNumber( int num )
004:    	{
005:    		// 1以下は素数ではない
006:    		if ( 1 >= num ) return false;
007:    
008:    		// 2の場合は素数
009:    		if ( 2 == num ) return true;
010:    
011:    		// 素数判定
012:    		int n = (int)Math.sqrt( num );
013:    		for ( int i = 2; i <= n; ++ i ) {
014:    			// 余り0で割り切れるかを判定
015:    			if ( 0 == ( num % i ) ) return false;
016:    		}
017:    
018:    		// numが2～nで割り切れなかったので素数
019:    		return true;
020:    	}
021:    
022:    
023:    	// メイン
024:    	public static void main( String[] args ) {
025:    		// 変数の宣言
026:    		int number;	// 素数かどうか調べる整数値
027:    
028:    		// 入力した引数が１つ以上かを調べる
029:    		if ( 1 > args.length ) {
030:    			// 入力した引数が１つ未満の場合、使用方法を表示する
031:    			System.out.println( "PrimeNumber1 [整数値]" );
032:    			return;
033:    		}
034:    
035:    
036:    		// 引数をint型に変換しnumberに代入
037:    		try {
038:    			number = Integer.parseInt( args[ 0 ] );
039:    		}
040:    		catch( NumberFormatException ne )
041:    		{
042:    			// args[0]が数字ではない
043:    			System.out.println( "[整数値]の取得に失敗しました" );
044:    			return;
045:    		}
046:    
047:    		// 素数かどうか調べる
048:    		if ( true == isPrimeNumber( number ) )
049:    			System.out.println( number + "は素数です" );
050:    		else
051:    			System.out.println( number + "は素数ではない" );
052:    	}
053:    }

PrimeNumber1を実行

C:\talavax\javasample>java PrimeNumber1 5

１つ目の引数に5を渡して、素数かどうか調べます。

実行結果

5は素数です

素数はどうかを判定するisPrimeNumberメソッドの説明をします。

003:    	private static boolean isPrimeNumber( int num )

int型の変数numが素数であればtrue、素数でなければfalseを返すisPrimeNumberメソッドを作成しています。

005:    		// 1以下は素数ではない
006:    		if ( 1 >= num ) return false;

numが1以下の場合、素数ではないのでfalseを返しています。

008:    		// 2の場合は素数
009:    		if ( 2 == num ) return true;

numが2の場合、素数なのでtrueを返しています。

011:    		// 素数判定
012:    		int n = (int)Math.sqrt( num );
013:    		for ( int i = 2; i <= n; ++ i ) {
014:    			// 余り0で割り切れるかを判定
015:    			if ( 0 == ( num % i ) ) return false;
016:    		}

numを2～nまでの整数で順番に割っていき、割り切れたら素数ではないのでfalseを返しています。ここで、n=(int)√numはnumの平方根の小数点以下を切り捨てた整数値です。

018:    		// numが2～nで割り切れなかったので素数
019:    		return true;

numを2～nまでの整数で順番に割っていき、割り切れなかったら素数なのでtrueを返しています。

■他の素数の求め方

素数リスト作成

素数リストの作成方法を解説

■関連コンテンツ

平方根	Math.sqrtの使い方について解説

	剰余(余り)計算剰余(余り)をを計算するプログラムの紹介と、その結果を表示する方法を解説
	for文繰り返し処理に使用するfor文をJavaのソースコードを使って説明しています。
	計算結果の表示足し算(加法)／引き算(減法)／掛け算(乗法)／割り算(除法)の使い方を説明