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;
				}
			}
		}
	}
}

実行結果

素因数分解する整数に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 );

変数iprintlnコンソール出力します。

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のソースコードを使って解説しています。

2020.03.23

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

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

2016.02.01

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

2016.02.02

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

2020.03.23

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

2022.08.28

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

2022.08.28

広告