最大公約数が最も大きい組み合わせを見つける(Java版)

Exercise.java

import java.util.List;
import java.util.ArrayList;
import java.util.Set;
import java.util.HashSet;
import java.util.Collections;

public class Exercise {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>();
        for (String str : args)
            nums.add(Integer.parseInt(str));

        Set<Pair> combination = new HashSet<>();
        for (int i = 0; i < nums.size(); i++) {
            int a = nums.get(i);
            for (int b : nums.subList(i + 1, nums.size()))
                combination.add(new Pair(a, b));
        }

        exercise1(combination);
        exercise2(combination, Collections.max(nums));
    }

    private static void exercise1(Set<Pair> combination) {
        int maxGCD = 0;
        Set<Pair> result = new HashSet<>();
        for (Pair pair : combination) {
            int gcd = gcd(pair.max, pair.min);
            if (gcd > maxGCD) {
                maxGCD = gcd;
                result.clear();
                result.add(pair);
            } else if (gcd == maxGCD) {
                result.add(pair);
            }
        }
        System.out.println("Exercise 1");
        System.out.println("GCD:" + maxGCD);
        System.out.println("Pairs:" + result);
    }

    private static void exercise2(Set<Pair> combination, int maxNum) {
        List<Integer> primeList = PrimeNum.getPrimeList(maxNum);
        int maxCDCount = 0;
        Set<Pair> result = new HashSet<>();
        for (Pair pair : combination) {
            int gcd = gcd(pair.max, pair.min);
            int aCDCount = countDivisor(gcd, primeList);
            if (aCDCount > maxCDCount) {
                maxCDCount = aCDCount;
                result.clear();
                result.add(pair);
            } else if (aCDCount == maxCDCount) {
                result.add(pair);
            }
        }
        System.out.println("Exercise 2");
        System.out.println("CDCount:" + maxCDCount);
        System.out.println("Pairs:" + result);
    }

    private static int gcd(int max, int min) {
        int residue = max % min;
        return (residue == 0) ? min : gcd(min, residue);
    }

    private static int countDivisor(int num, List<Integer> primeList) {
        List<Integer> exponentList = new ArrayList<>();
        for (int prime : primeList) {
            if (num == 1) break;
            int cnt = 0;
            for (; num % prime == 0; cnt++)
                num /= prime;
            if (cnt != 0)
                exponentList.add(cnt);
        }
        int result = 1;
        for (int cnt : exponentList)
            result *= cnt + 1;
        return result;
    }

    private static class Pair {
        final int min;
        final int max;
        Pair(int a, int b) {
            min = Math.min(a, b);
            max = Math.max(a, b);
        }
        @Override public int hashCode() {
            return 17 * min + max;
        }
        @Override public boolean equals(Object other) {
            boolean result = other instanceof Pair;
            if (result) {
                Pair tmp = (Pair) other;
                result = (tmp.min == min) && (tmp.max == max);
            }
            return result;
        }
        @Override public String toString() {
            return "(" + min + ", " + max + ")";
        }
    }
}

class PrimeNum {
    static List<Integer> getPrimeList(int max) {
        List<Integer> primeList = new ArrayList<>();
        if (max > 1) {
            primeList.add(2);
            for (int i = 3; i <= max; i += 2)
                if (isPrime(i, primeList))
                    primeList.add(i);
        }
        return primeList;
    }
    private static boolean isPrime(int num, List<Integer> primeList) {
        boolean notPrime = false;
        int max = (int) Math.sqrt(num);
        for (int prime : primeList)
            if (prime > max || (notPrime = (num % prime == 0)))
                break;
        return ! notPrime;
    }
}