2016.02.01

数学

素数判定

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

2、3、5、7、11、13、17、19、23 …

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

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

判定する例として素数である11で説明します。この場合√11の整数部は3です。2から3の値で11を割っていき、割り切れなければ素数としています。ここで、なぜ3(=√Nの整数部)より大きい整数で割る必要がないかを考えます。11を4で割ったは2で余り3です。11を5で割ったは2で余り1です。11を6で割ったは1で余り5です。このようにが3より大きい値になりません。よって、仮に4と5で割り切れるなら、2か3でも割り切れていたはずです。よって、√Nを割る数の上限にしています。

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

Javaソースコード

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

PrimeNumber1.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
053
public class PrimeNumber1 {
	// 素数判定メソッド
	private static boolean isPrimeNumber( int num )
	{
		// 1以下は素数ではない
		if ( 1 >= num ) return false;

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

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

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


	// メイン
	public static void main( String[] args ) {
		// 変数の宣言
		int number;	// 素数かどうか調べる整数値

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


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

		// 素数かどうか調べる
		if ( true == isPrimeNumber( number ) )
			System.out.println( number + "は素数です" );
		else
			System.out.println( number + "は素数ではない" );
	}
}

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

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

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

C:\talavax\javasample>javac PrimeNumber1.java

実行

C:\talavax\javasample>java PrimeNumber1 5

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

出力結果

5は素数です

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

003
	private static boolean isPrimeNumber( int num )

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

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

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

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

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

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

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

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

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

以上です。

次のコンテンツ

配列を使って素数を判定するプログラムを紹介しています。是非、ご覧ください。

2016.02.02

関連コンテンツ

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

2022.10.25

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

2023.01.03

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

2020.03.23

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

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

2023.03.20

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

2020.03.20

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

2020.03.23

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

2022.12.13

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

2020.03.23

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

2020.03.23

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

2020.03.23

配列を使って素数を判定するプログラムを紹介しています。是非、ご覧ください。

2016.02.02

平方根の意味と、Math.sqrtメソッドの使い方をソースコードを使って詳しく解説しています。

2020.03.23

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

2020.03.23

割り算で割り切れずに残った端数を剰余(余り)といいます。この剰余の計算をJavaのソースコードを使って解説しています。

2020.03.23

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

2022.08.03

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

2020.03.23

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

2022.08.29

最大公約数について解説しています。興味がある方はご覧ください。

2020.07.08

素因数分解は、自然数を素数の積(掛け算)で表すことです。この記事では、素因数分解のJavaのソースコードを解説しています。

2022.08.25

広告