Javaで数値の最大の素因数を求めるプログラムの書き方

本記事では、与えられた数値の最大の素因数を求めるためのJavaプログラムを紹介します。素因数分解の基本的なアルゴリズムを理解することで、効率的な計算方法を身につけることができます。

素因数とは？

素因数とは、ある整数を素数だけの積で表したときに現れる素数のことです。たとえば、148592を素因数分解すると、その最大の素因数は251になります。

サンプルコード

以下は、数値の最大の素因数を求めるJavaコードです。

import java.io.*;
import java.util.*;
public class Demo{
    static long maxPrimeFactors( long val){
        long max_prime = -1;
        while (val % 2 == 0) {
            max_prime = 2;
            val >>= 1;
        }
        for (int i = 3; i <= Math.sqrt(val); i += 2){
            while (val % i == 0){
                max_prime = i;
                val = val / i;
            }
        }
        if (val > 2)
        max_prime = val;
        return max_prime;
    }
    public static void main(String[] args){
        int val = 148592;
        System.out.println("The largest prime factor of 148592 is ");
        System.out.println(maxPrimeFactors(val));
        val = 890654;
        System.out.println("The largest prime factor of 890654 is ");
        System.out.println(maxPrimeFactors(val));
    }
}

実行結果

The largest prime factor of 148592 is
251
The largest prime factor of 890654 is
4591

コードの解説

Demoというクラスの中には、long型の値を受け取るstaticメソッドmaxPrimeFactorsが定義されています。まず最初のwhileループでは、値を2で割った余りが0かどうかを判定します。余りが0である間は、変数max_primeに2を代入し、値を1ビット右シフト（2で割る操作と同等）していきます。これにより、偶数の要素をすべて取り除くことができます。

次にforループを使用し、3から値の平方根までの奇数を2ずつ増やしながら反復処理を行います。この中でさらにwhileループにより、値を現在の反復子iで割った余りが0かどうかを確認します。割り切れる場合は、max_primeにその反復子の値を代入し、値をiで割り続けます。平方根まで調べれば十分なのは、それより大きい約数は必ず小さい約数とペアになるためです。

すべての処理が完了した後、残った値が2より大きい場合、その値自体が最大の素因数となるため、max_primeに代入して返します。

mainメソッドでは、整数値148592と890654を定義し、それぞれを引数としてmaxPrimeFactorsメソッドを呼び出すことで、最大の素因数を求めてコンソールに出力しています。