2022.08.25

数学

素因数分解(prime factorization)

素因数分解は、自然数素数の積(掛け算)で表すことです。

自然数素因数分解した例を見ていきましょう。以下の例は、8、12、200、321、555、733をそれぞれ素因数分解したものです。

8=2×2×2
12=2×2×3
200=2×2×2×5×5
321=3×107
555=3×5×37
733=733

右辺の素数掛け算が左辺と一致していることが分かります。733は素数なので、右辺を掛け算の式で書いていません。

素因数分解のプログラムの作り方

与えられた自然数Nに対して以下の①~③処理を行って、素因数分解します。

①Nを2、3、4、・・、Nの順番で割っていき、余りが0になったときの値を出力し、割り算をやめます。

②Nを出力した値で割ります。

③Nが1になったとき処理を終了します。Nが1より大きい場合は、Nで①の処理を行います。

ここで自然数N=105を使って、上記の①~③処理を追ってみます。

①N=105は3で割り切れるので「3」を出力します。

②N=105を「3」で割ります。N=105÷3=35

③Nは1ではないので、①の処理に戻ります。

①N=35は5で割り切れるので「5」を出力します。

②N=35を「5」で割ります。N=35÷5=7

③Nは1ではないので、①の処理に戻ります。

①N=7は7で割り切れるので「7」を出力します。

②N=7を「7」で割ります。N=7÷7=1

③Nは1なので、処理を終了します。

自然数N=105で、「3」と「5」と「7」の3つの数が出力されました。これが素因数分解の結果です。

105=3×5×7

Javaソースコード(whileを使用)

任意の自然数素因数分解を行うJavaソースコードです。自然数に1以下を与えた場合は、処理を実行しません。

PrimeFactors1.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
import java.util.Scanner;

class PrimeFactors1 {
	public static void main( String[] args ) {
		// Scannerを作成
		Scanner scan = new Scanner( System.in );

		// 入力した文字列をnに格納
		System.out.print( "素因数分解する整数:" );
		int n = scan.nextInt();

		// 整数nが1以下であれば、処理を中断
		if ( 1 >= n ) {
			System.out.print( "2以上の整数を入力してください" );
			return;
		}

		// 素因数分解
		// nが1以下のときに抜けるループ
		while ( 1 < n ) {
			// nを2から順番に割っていく
			for ( int i = 2; i <= n; i ++ ) {
				if ( 0 == ( n % i ) )
				{
					// nがiで割り切れたときの処理

					// 素数iをコンソール出力(改行付き)
					System.out.println( i );

					// nをiで割る
					n = n / i;

					// nが再度iで割り切れる可能性があるのでfor文を抜ける
					break;
				}
			}
		}
	}
}

実行結果

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

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

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

C:\talavax\javasample>javac PrimeFactor1.java

素因数分解する整数に12を入力して実行

C:\talavax\javasample>java PrimeFactor1
素因数分解する整数:12

出力結果

2
2
3

3行に分かれて出力された2と2と3を掛け合わせると、2×2×3=12となります。

素因数分解する整数に555を入力して実行

C:\talavax\javasample>java PrimeFactor1
素因数分解する整数:555

出力結果

3
5
37

3行に分かれて出力された3と5と37を掛け合わせると、3×5×37=555となります。

Javaソースコードの解説

001
import java.util.Scanner;

Javaクラスライブラリの中から「java.util.Scanner」というパッケージにあるクラスを、このプログラム内で使うために記述します。 この記述により、Scannerクラスが利用できるようになります。これでキーボードから値の入力が行えるようになります。

003
class PrimeFactors1 {

クラス名を、PrimeFactors1としています。

004
	public static void main( String[] args ) {

このmainメソッドからプログラムを実行します。

005
006
		// Scannerを作成
		Scanner scan = new Scanner( System.in );

Scannerクラスを作成しています。

008
009
010
		// 入力した文字列をnに格納
		System.out.print( "素因数分解する整数:" );
		int n = scan.nextInt();

キーボードから入力した素因数分解する整数int型変数nに代入します。入力した値が整数値で無い場合、エラーを表示してプログラムを強制終了します。10.0など小数点付の数値もエラーになります。

012
013
014
015
016
		// 整数nが1以下であれば、処理を中断
		if ( 1 >= n ) {
			System.out.print( "2以上の整数を入力してください" );
			return;
		}

変数nが1以下の場合に、printコンソールにメッセージを出力し、return文mainメソッドを抜けます。

018
019
020
		// 素因数分解
		// nが1以下のときに抜けるループ
		while ( 1 < n ) {

変数nが1より大きい場合に繰り返すwhile文です。nが1になるとwhile文を抜けます。

021
022
			// nを2から順番に割っていく
			for ( int i = 2; i <= n; i ++ ) {

変数nを割っていく変数iを2からnまで変化させるfor文です。

023
024
				if ( 0 == ( n % i ) )
				{

変数n変数i割り切れるかを判定しています。nをiで割った余りが0の場合、割り切れたと判定しています。

025
026
027
028
					// nがiで割り切れたときの処理

					// 素数iをコンソール出力(改行付き)
					System.out.println( i );
030
031
					// nをiで割る
					n = n / i;

変数n変数iで割ります。

033
034
					// nが再度iで割り切れる可能性があるのでfor文を抜ける
					break;

for文break文を使って抜けます。

変数nが1になると、while文を抜けて処理が終了します。

Javaソースコード(forを使用)

任意の自然数素因数分解を行うJavaソースコードです。

PrimeFactors2.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
import java.util.Scanner;

class PrimeFactors2 {
	public static void main( String[] args ) {
		// Scannerを作成
		Scanner scan = new Scanner( System.in );

		// 入力した文字列をnに格納
		System.out.print( "素因数分解する整数:" );
		int n = scan.nextInt();

		// 整数nが1以下であれば、処理を中断
		if ( 1 >= n ) {
			System.out.print( "2以上の整数を入力してください" );
			return;
		}

		// 素因数分解
		// 無限ループ
		for ( ; ; ) {
			// nが1以下のとき、for文を抜ける
			if ( 1 >= n ) break;

			// nを2から順番に割っていく
			for ( int i = 2; i <= n; i ++ ) {
				if ( 0 == ( n % i ) )
				{
					// nがiで割り切れたときの処理

					// 素数iをコンソール出力(改行付き)
					System.out.println( i );

					// nをiで割る
					n = n / i;

					// nが再度iで割り切れる可能性があるのでfor文を抜ける
					break;
				}
			}
		}
	}
}

Javaソースコードの解説

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
import java.util.Scanner;

class PrimeFactors2 {
	public static void main( String[] args ) {
		// Scannerを作成
		Scanner scan = new Scanner( System.in );

		// 入力した文字列をnに格納
		System.out.print( "素因数分解する整数:" );
		int n = scan.nextInt();

		// 整数nが1以下であれば、処理を中断
		if ( 1 >= n ) {
			System.out.print( "2以上の整数を入力してください" );
			return;
		}

ここまでは、「PrimeFactors1.Java」とほぼ同じなので説明を省略します。クラス名が違うだけです。

018
019
020
		// 素因数分解
		// 無限ループ
		for ( ; ; ) {

for文で作った無限ループです。終了条件を書いてないので、無限にfor文の中の処理を繰り返します。

021
022
			// nが1以下のとき、for文を抜ける
			if ( 1 >= n ) break;

変数nが1以下の場合に、break文無限ループを抜けるようにしています。

024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
			// nを2から順番に割っていく
			for ( int i = 2; i <= n; i ++ ) {
				if ( 0 == ( n % i ) )
				{
					// nがiで割り切れたときの処理

					// 素数iをコンソール出力(改行付き)
					System.out.println( i );

					// nをiで割る
					n = n / i;

					// nが再度iで割り切れる可能性があるのでfor文を抜ける
					break;
				}

ここは、「PrimeFactors1.Java」と同じなので説明を省略します。

変数nが1になると、for文を抜けて処理が終了します。

以上です。

素因数分解に関係するコンテンツ

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

2022.10.25

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

2020.03.23

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

素数を判定するプログラムを作成してみませんか?興味のある方は、ご覧ください。

2016.02.01

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

2016.02.02

for文を使って、数字を順番に増やす方法を詳しく説明しています。

2022.08.28

for文を使って、数字を順番に減らす方法を詳しく説明しています。

2022.08.28

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

2020.03.23

日本で使われてきた伝統文様「和柄」について解説しています。

2022.07.27

画像フォーマット形式・色・大きさ・傾きなどの変更、特定の図形(文字・記号など)を見つけたり、取り出したりする画像処理について詳しく解説。

2015.11.29

プログラミング、ITに関する用語をまとめています。

2022.10.17

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

2020.03.23

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

2023.03.20

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

2020.03.20

処理を繰り返すために使用するwhile文について解説しています。

2016.01.26

繰り返し処理の作り方を解説しています。

2016.03.02

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

2022.12.13

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

2020.03.23

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

2020.03.23

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

2020.03.23

繰り返し処理(ループ)から強制的に抜けかたについて解説しています。

2017.07.14

Javaのプログラムを作ってみませんか?プログラミングに必要なものの用意から実行までを説明しています。

2020.03.23

Javaの学習に役立つソースコードを多数紹介しています。是非、ご覧ください。

2022.09.10

Swingパッケージを使ってグラフィック表示を行う方法を解説しています。

2020.03.23

繰り返し処理を使ったJavaのソースコードサンプルを紹介しています。

2020.03.23

配列を使うJavaソースコードを多数紹介しています。

2021.05.18

三角形、台形、円などいろいろな図形の面積を計算するプログラムを紹介しています。詳しくは、記事をご覧ください。

2021.05.18

StringクラスとStringBuilderクラスを利用したプログラミングの仕方を紹介しています。

2016.12.16

Javaを使った簡単な応用プログラム(生年月日から年齢を計算プログラムなど)を紹介しています。

2022.07.07

関連コンテンツ

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

2020.03.23

素数を判定するプログラムを作成してみませんか?興味のある方は、ご覧ください。

2016.02.01

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

2020.03.23

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

2020.03.23

Javaの演算子'/'を使って割り算を行った結果と注意点などについて説明。

2020.03.23

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

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

2022.08.03

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

2020.03.23

Javaプログラムの構成について解説しています。詳しくは、こちらをご覧ください。

2020.03.23

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

2022.12.13

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

2022.08.29

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

2020.03.23

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

2020.03.23

コンピュータを制御するために使用する入力機能と出力機能を持つ装置のことをコンソールといいます。興味のある方は、ご覧ください。

2020.08.24

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

2020.03.20

処理を繰り返すために使用するwhile文について解説しています。

2016.01.26

処理を繰り返すために使用するfor文について解説しています。

2020.03.23

繰り返し処理(ループ)から強制的に抜けかたについて解説しています。

2017.07.14

繰り返し処理の作り方を解説しています。

2016.03.02

「ゆるゆるプログラム」のコンテンツを紹介しています。興味のある方はこの記事をご覧ください。

2020.03.23

Javaの学習に役立つソースコードを多数紹介しています。是非、ご覧ください。

2022.09.10

Javaを使った簡単な応用プログラム(生年月日から年齢を計算プログラムなど)を紹介しています。

2022.07.07

Swingパッケージを使ってグラフィック表示を行う方法を解説しています。

2020.03.23

画像フォーマット形式・色・大きさ・傾きなどの変更、特定の図形(文字・記号など)を見つけたり、取り出したりする画像処理について詳しく解説。

2015.11.29

三角形、台形、円などいろいろな図形の面積を計算するプログラムを紹介しています。詳しくは、記事をご覧ください。

2021.05.18

配列を使うJavaソースコードを多数紹介しています。

2021.05.18

繰り返し処理を使ったJavaのソースコードサンプルを紹介しています。

2020.03.23

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

2022.10.25

StringクラスとStringBuilderクラスを利用したプログラミングの仕方を紹介しています。

2016.12.16

日本で使われてきた伝統文様「和柄」について解説しています。

2022.07.27

プログラミング、ITに関する用語をまとめています。

2022.10.17

広告