ゆるゆるプログラミング

・素数判定

素数とは1と自分自身でだけで割り切れる2以上の数です。(1は素数ではありません)

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

以下が、素数判定の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:    		// 入力した引数が1つ以上かを調べる
029:    		if ( 1 > args.length ) {
030:    			// 入力した引数が1つ未満の場合、使用方法を表示する
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

1つ目の引数に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の平方根の小数点以下を切り捨てた整数値です。割り切れるかの判定をnで打ち切れる理由は、numをnより大きい数値で割った商はn以下になり、nより大きい数値で割り切れるなら、n以下の商で既に割り切れているためです。(分かりづらかったらゴメンなさい)

例として11の素数で説明します。この場合n=(int)√11=3です。このソースコードに当てはめるとi=2~3の値で11を割っていき、割り切れなければ素数としています。ここで、なぜ3より大きい整数で割る必要がないかを考えます。11を4で割った商は2で余り3です。11を5で割った商は2で余り1です。11を6で割った商は1で余り5です。このように商が3より大きい値になりません。よって、仮に4と5で割り切れるなら、2か3でも割り切れていたはずです。

こんな感じです。

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

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

■他の素数の求め方

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

■関連コンテンツ

平方根 Math.sqrtの使い方について解説
for文 繰り返し処理に使用するfor文について解説

■新着情報

2017.11.17 N値化 カラー画像をN値化する方法について解説
2017.11.16 最も近い値の取得 指定値に最も近い配列の値を取得する方法を解説
2017.10.02 アルファ値(透過) アルファ値(透過)について

■広告

法人向けのETC専用カード

~約8,000名の受講生と80社以上の導入実績~ 企業向けプログラミング研修ならCodeCamp

日本最大級ショッピングサイト!お買い物なら楽天市場

Topへ