Project EulerのProblem 51～52をやってみた

2017年5月3日Project EulerをJavaで解く

こんにちは。「Javaを復習する初心者」です。Project Eulerという数学の問題サイトがあります。そのサイトのProblem 51から52を解いてみました。

Problem 51

自分なりに直訳してみました。

    private void test() {
        for (int i = 11; i < 10000000; i++) {
            if (checkPrimaryOf(i)) {
                // 素数の場合

                List<Integer> list = getSameDigitsOf(i);
                if (!list.isEmpty()) {
                    // 同じ数字の桁を持つ場合、置換して素数が8個生成されるかを調べる。
                    for (int j = 0; j < list.size(); j++) {
                        int targetNumber = list.get(j);
                        if (targetNumber <= 2) {
                            List<Integer> numbers = getPrimesReplaced(i, targetNumber);
                            if (check(numbers)) {
                                System.out.println(i);
                                return ;
                            }
                        }
                    }
                } else {
                    // それ以外の場合、0、1、2を置換して、素数が8個生成されるかを調べる。
                    String s = String.valueOf(i);
                    for (int j = 0; j <= 2; j++) {
                        if (s.contains(String.valueOf(j))) {
                            List<Integer> numbers = getPrimesReplaced(i, j);
                            if (check(numbers)) {
                                System.out.println(i);
                                return ;
                            }
                        }
                    }
                }
            }
        }
    }

    private boolean checkPrimaryOf(int n) {
        int sqrt = (int) Math.sqrt(n);
        for (int i = 2; i <= sqrt; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    private List<Integer> getSameDigitsOf(int n) {
        List<Integer> list = new ArrayList<>();

        String s = String.valueOf(n);
        for (int i = 0; i <= 9; i++) {
            int count = 0;
            for (int j = 0; j < s.length(); j++) {
                if (i == s.charAt(j) - '0') {
                    count ++;
                }
            }

            if (count > 1) {
                list.add(i);
            }
        }

        return list;
    }

    private List<Integer> getPrimesReplaced(int n, int targetNumber) {
        List<Integer> list = new ArrayList<>();
        for (int i = targetNumber; i <= 9; i++) {
            String s = String.valueOf(n);
            s = s.replace((char)(targetNumber + '0'), (char)(i + '0'));
            list.add(Integer.valueOf(s));
        }
        return list;
    }

    private boolean check(List<Integer> list) {
        int count = 0;
        for (int i = 0; i < list.size(); i++) {
            if (checkPrimaryOf(list.get(i))) {
                count ++;
            }
        }
        if (count == 8) {
            System.out.println(list);
            return true;
        }
        return false;
    }

答えとなる数字は素数であることから、まず、素数であるかを判定することにしました。checkPrimaryOf()メソッドで判定しています。

素数に対して、各桁を見て同じ数字が含まれているかどうかで処理を変えています。同じ数字が含まれている場合、それを基に同じ数字を0から9で置換した数を取得することにしました。getPrimesReplaced()メソッドです。メソッド名は適切ではないかもしれません。置換した数字はListで返却することにしています。

check()というメソッドは引数に指定されたListオブジェクトが8個の素数を含むか判定するメソッドです。適切なメソッド名が思い浮かばなかったので、このようなメソッド名にしています。8個の素数を含む場合、題意を満たす素数が求まるということです。

else文の箇所「それ以外の場合、0、1、2を置換して、素数が8個生成されるかを調べる。」という処理は、素数の各桁を見て同じ数字を持たない場合です。問題文の文言から、このパターンはなさそうなのですが念のため処理をしています。

Problem 52

自分なりに直訳してみました。

    private void test() {
        for (int i = 10; i < 300000; i++) {
            String s = String.valueOf(i);
            if (checkDigits(s, String.valueOf(2 * i))
                    && checkDigits(s, String.valueOf(3 * i))
                    && checkDigits(s, String.valueOf(4 * i))
                    && checkDigits(s, String.valueOf(3 * i))
                    && checkDigits(s, String.valueOf(5 * i))
                    && checkDigits(s, String.valueOf(6 * i))) {
                System.out.println(s);
                return ;
            }
        }
    }

    private boolean checkDigits(String s, String t) {
        // 桁数が等しいか判定
        if (s.length() != t.length()) {
            return false;
        }

        int[] counts = new int[s.length()];
        // sのi番目に対して、tのj番目が等しい場合、counts[i]を加算
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            for (int j = 0; j < t.length(); j++) {
                if (c == t.charAt(j)) {
                    counts[i] ++;
                }
            }
        }
        // counts[i]がすべて1ならtrueを返却
        for (int i = 0; i < counts.length; i++) {
            if (counts[i] != 1) {
                return false;
            }
        }
        return true;

    }

メソッド「private boolean checkDigits(String s, String t)」を定義しました。tがsと同じ数字を各桁に持つかというのを判定するメソッドです。第1引数に自然数x、第2引数に2xから6xを指定するという想定です。

最初にsとtの桁数が等しいか判定しています。桁数が異なるならば、題意を満たしていないため、最初にこの判定処理をしています。

後の処理ではString#charAt()メソッドを使いました。i番目の文字を取り出すメソッドです。このメソッドを使って、sの各桁について、tの方で何度出現しているかを算出しています。これでtのほうで出現回数がすべて1回ならば、tはsの桁の数字を変えただけということなります。

上記メソッドを使い、for文で300000未満まで調べました。この数は適当です。出力がなかったら大きくするという方針でやりました。