2022.08.25
数学
素因数分解(prime factorization)
８＝２×２×２ １２＝２×２×３ ２００＝２×２×２×５×５ ３２１＝３×１０７ ５５５＝３×５×３７ ７３３＝７３３
素因数分解のプログラムの作り方
与えられた自然数Ｎに対して以下の①～③処理を行って、素因数分解します。
①Ｎを２、３、４、・・、Ｎの順番で割っていき、余りが０になったときの値を出力し、割り算をやめます。
②Ｎを出力した値で割ります。
③Ｎが１になったとき処理を終了します。Ｎが１より大きい場合は、Ｎで①の処理を行います。
ここで自然数Ｎ＝１０５を使って、上記の①～③処理を追ってみます。
自然数Ｎ＝１０５で、「３」と「５」と「７」の３つの数が出力されました。これが素因数分解の結果です。
１０５＝３×５×７
Javaソースコード(whileを使用)
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
素因数分解する整数に１２を入力して実行
C:\talavax\javasample>java PrimeFactor1 素因数分解する整数:12
出力結果
2 2 3
３行に分かれて出力された２と２と３を掛け合わせると、２×２×３＝１２となります。
素因数分解する整数に５５５を入力して実行
C:\talavax\javasample>java PrimeFactor1 素因数分解する整数:555
出力結果
3 5 37
３行に分かれて出力された３と５と３７を掛け合わせると、３×５×３７＝５５５となります。
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();
012 013 014 015 016
// 整数nが1以下であれば、処理を中断 if ( 1 >= n ) { System.out.print( "2以上の整数を入力してください" ); return; }
018 019 020
// 素因数分解 // nが1以下のときに抜けるループ while ( 1 < n ) {
021 022
// nを2から順番に割っていく for ( int i = 2; i <= n; i ++ ) {
023 024
if ( 0 == ( n % i ) )
{
025 026 027 028
// nがiで割り切れたときの処理 // 素数iをコンソール出力（改行付き） System.out.println( i );
030 031
// nをiで割る
n = n / i;
033 034
// nが再度iで割り切れる可能性があるのでfor文を抜ける break;
Javaソースコード(forを使用)
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; }
018 019 020
// 素因数分解 // 無限ループ for ( ; ; ) {
021 022
// nが1以下のとき、for文を抜ける
if ( 1 >= n ) 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」と同じなので説明を省略します。
以上です。
素因数分解に関係するコンテンツ
割り算で「割り切れる」、「割り切れない」ってどういうこと？
関連コンテンツ
割り算で「割り切れる」、「割り切れない」ってどういうこと？
広告
