算術の基本定理

素数と素因数の基礎概念

算術の基本定理を理解するにあたり、まず基本となる用語を整理しておこう。素数とは、2以上の自然数のうち、1とその数自身以外では割り切れない数を指す。代表的な素数としては2、3、5、7、11などが挙げられる。一方、素因数とは、ある整数を構成する素数のことを意味する。例えば、12という数は2×2×3という積で表わされるが、この場合の2と3が素因数である。

算術の基本定理の定義

算術の基本定理は、数論における最も基本的な定理の一つである。この定理は「2以上の任意の整数は、素数の積として一意に表現できる」と主張する。ここでいう「一意」とは、積の順序が異なるだけのものは同一視されるという前提のもとで、異なる素因数の組からは同じ整数が得られないことを意味する。

定理の証明 - 存在性と一意性

算術の基本定理の証明は、存在性の証明と一意性の証明という二つの部分から構成される。

существова性（構成的可能性）の証明においては、背理法を用いたアプローチが有効である。2以上の整数で素因数分解できないものが存在すると仮定する。その際、分解できない整数のうち最小のものを考える。その整数は1でも自分自身でも割り切れるため、自身の約数を持たなければならない。そして、その約数は合成数ではなく素数でなければならない。結局、その整数は素数と別の整数の積として表せ、これは仮定に反する。

一意性の証明では、同一の整数が二つの異なる素因数分解を持つと仮定して矛盾を導く。最小の素因数を比較することで二つの分解式が同じ素因数を持たざるを得ず、矛盾が生じる。したがって、素因数分解は順序の違いを除いて一意である。

Javaによる素因数分解の実装例

以下に、素因数分解を行うJavaプログラムを示す。この実装では、2から順に除算を行いながら最小の素因数を探していく方式を採用している。

import java.util.InputMismatchException;
import java.util.Scanner;

public class PrimeDecomposer {
    public static void main(String[] args) {
        try (Scanner scanner = new Scanner(System.in)) {
            System.out.print("2以上の整数を入力してください: ");
            int targetNumber = scanner.nextInt();
            decomposePrimeFactors(targetNumber);
        } catch (InputMismatchException e) {
            System.out.println("整数以外の入力は許可されていません。");
        }
    }

    private static void decomposePrimeFactors(int number) {
        if (number < 2) {
            System.out.println("2以上の整数を入力してください。");
            return;
        }

        StringBuilder expression = new StringBuilder();
        int remainder = number;
        int divisor = 2;

        while (divisor <= remainder) {
            while (remainder % divisor == 0) {
                if (expression.length() > 0) {
                    expression.append(" × ");
                }
                expression.append(divisor);
                remainder /= divisor;
            }
            divisor++;
        }

        System.out.println(number + " = " + expression.toString());
    }
}

実践例：素因数分解の問題

問題設定

任意の2以上の整数が与えられたとき、その数を素因数の積として分解するプログラムを作成せよ。

実行例

入力値として60を与えた場合、出力は「60 = 2 × 2 × 3 × 5」となる。

解答プログラム

import java.util.Scanner;

public class FactorizationPractice {
    public static void main(String[] args) {
        Scanner inputReader = new Scanner(System.in);
        System.out.print("分解したい整数（2以上）を入力: ");
        int value = inputReader.nextInt();
        inputReader.close();

        if (value < 2) {
            System.out.println("エラー: 2以上の値を入力してください。");
            return;
        }

        StringBuilder resultBuilder = new StringBuilder();
        int currentValue = value;
        int trialDivisor = 2;

        while (trialDivisor <= currentValue) {
            while (currentValue % trialDivisor == 0) {
                if (resultBuilder.length() != 0) {
                    resultBuilder.append(" × ");
                }
                resultBuilder.append(trialDivisor);
                currentValue /= trialDivisor;
            }
            trialDivisor++;
        }

        System.out.println("分解結果: " + resultBuilder.toString());
    }
}

計算過程の解説

60を素因数分解する場合、まず2で割れるだけ割っていく。60÷2=30、30÷2=15となり、2で二度割ったところで15になる。次に3で割ると15÷3=5となる。最後に5で割ると1になる。以上の操作から、60=2×2×3×5という分解が得られる。

計算量に関する考察

このアルゴリズムの時間計算量はO(√n)である。√nまで試除すれば十分であり、それ以上の除算は合成数による除算でカバーされるためである。