Zenn
🎯

【Java】素因数分解と約数の個数

2024/03/25に公開
Java
初心者
tech

素因数分解

180を素因数分解すると、

180 = 2^2 × 3^2 × 5^1

となります。

問題

n = 180 を素因数分解した時の結果を標準出力に出力せよ。

答え

2
2
3
3
5

コード例

import java.util.*;

public class Main {
    // 整数 n=180 を受け取り、素因数分解をおこなって (素因数＝指数) の連想配列を返す
    static HashMap<Integer, Integer> factorize(int n) {
        HashMap<Integer, Integer> primes = new HashMap<>();

        for (int i = 2; i * i <= n; i++) {
            if (n % i > 0) {
                continue;
            }
            int exp = 0;
            while (n % i == 0) {
                exp++;
                n /= i;
            }
            primes.put(i, exp);
        }

        if (n != 1) {
            primes.put(n, 1);
        }

        return primes;
    }

    public static void main(String[] args) {
        int n = 180;
        HashMap<Integer, Integer> table = factorize(n);
        for(int prime : table.keySet()){
            int exp = table.get(prime);
            for(int i = 0; i < exp; i++){
                System.out.println(prime);
            }
        }
    }
}

コード例の解説

mainメソッドのn = 180から順を追っていきたいと思います。
但し、標準出力に出力する過程の解説は割愛します。

  1. n = 180と定義します。
  2. factorizeメソッドを呼び出し、実引数としてnを渡します。
  3. factorizeメソッド内で、primesという連想配列を初期化します。
  4. 2から√ｎまでループするfor文を定義します。
  5. if文の条件式が、nをiで割った時の余りが0より大きい場合は、となっており、これは、結局のところnを割り切れないiの場合ということです。
  6. 上記がtrueなら、continueにより、iを1増やして、for文を進めます。
  7. nを割り切れるiの場合は、変数expを0で初期化します。(exp → exponent → 指数)
  8. while文の条件式n=180をi=2で割ると余りは0を満たすので、
  9. 変数expを1に更新します。
  10. n=90に更新します。
  11. while文の条件式n=90をi=2で割ると余りは0を満たすので、
  12. 変数expを2に更新します。
  13. n=45に更新します。
  14. while文の条件式n=45をi=2で割ると余りは0を満たさないので、while文を抜けます。
  15. 連想配列primesに2=2を代入します。
  16. iを1増やして、n=45をi=3は割り切れるので、if文には入らず、
  17. 変数expを0で初期化します。
  18. while文の条件式n=45をi=3で割ると余りは0を満たすので、
  19. 変数expを1に更新します。
  20. n=15に更新します。
  21. while文の条件式n=15をi=3で割ると余りは0を満たすので、
  22. 変数expを2に更新します。
  23. n=5に更新します。
  24. while文の条件式n=5をi=3で割ると余りは0を満たさないので、while文を抜けます。
  25. 連想配列primesに3=2を代入します。
  26. 以降、iを1増やしていき、i=4～13(√180は約13.4)までfor文をループしますが、どれも割り切れないため、continueにより、for文を進めるめることになり、このfor文からも抜けます。
  27. if文の条件式n=5 != 1を満たすので、
  28. 連想配列primesに5=1を代入します。
  29. 呼び出し元に戻り値として連想配列primesを返します。
    この時の連想配列primesは、下記の通りです。
    {2=2, 3=2, 5=1}

約数の個数

180の約数の個数は、素因数分解した各素因数の指数に1を足してからそれぞれを掛け合わせることで求めることができます。

180 = 2^2 × 3^2 × 5^1
(2+1) × (2+1) × (1+1) = 18

問題

n = 180 の約数の個数を標準出力に出力せよ。

答え

18

コード例

import java.util.*;

public class Main {
    // 素因数分解のものと全く同じ
    // 整数 n=180 を受け取り、素因数分解をおこなって (素因数＝指数) の連想配列を返す
    static HashMap<Integer, Integer> factorize(int n) {
        HashMap<Integer, Integer> primes = new HashMap<>();

        for (int i = 2; i * i <= n; i++) {
            if (n % i > 0) {
                continue;
            }
            int exp = 0;
            while (n % i == 0) {
                exp++;
                n /= i;
            }
            primes.put(i, exp);
        }

        if (n != 1) {
            primes.put(n, 1);
        }

        return primes;
    }

    // 返り値として連想配列 primes を受け取り、約数の個数を返す
    static int calcNumOfPrimeFactors(int n) {
        HashMap<Integer, Integer> primes = factorize(n);

        int numOfPrimeFactors = 1;
        
        for (int num : primes.values()) {
            numOfPrimeFactors *= (num + 1);
        }

        return numOfPrimeFactors;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int numOfPrimeFactors = calcNumOfPrimeFactors(n);

        System.out.println(numOfPrimeFactors);
    }
}

コード例の解説

factorizeメソッドは、素因数分解の時と全く同じなので、解説を割愛します。
calcNumOfPrimeFactorsメソッドについてのみ解説します。
まずは、連想配列primesは、下記の通りです。

{2=2, 3=2, 5=1}
  1. 変数numOfPrimeFactorsを1で初期化します。
  2. 拡張for文により、連想配列primesの1つ目のValue=2を、変数numに代入します。
  3. 変数numOfPrimeFactorsを3で更新します。
  4. 拡張for文により、連想配列primesの2つ目のValue=2を、変数numに代入します。
  5. 変数numOfPrimeFactorsを9で更新します。
  6. 拡張for文により、連想配列primesの3つ目のValue=1を、変数numに代入します。
  7. 変数numOfPrimeFactorsを18で更新します。
  8. 呼び出し元に戻り値として変数numOfPrimeFactorsを返します。

Discussion