ゆるゆるプログラミング

・素数判定

素数とは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文について解説

■新着情報

2020.06.03 円を描く(テキスト版) テキストを円を描く
2020.06.02 文字の間違い探し どの文字が違う?
2020.05.31 九九(くく)の表を作る2 掛け算なしで九九(くく)の表を作成
2020.05.07 サイコロの出目確率 サイコロの目のでる確率は?

■広告

フィギュア予約最大25%OFF+ポイント5%還元!ホビーサーチ

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

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

Topへ