hikoboshi2(java)

Hikoboshi.java

public class Hikoboshi {

    /**
     * 引数nの場合のオイラー関数の値を返す
     * @param n
     * @return
     */
    private static long phi(long n) {
        long result = n;

        //まず唯一の偶数の素数2で割れるだけ割る
        if (n % 2 == 0) {
            do {
                n /= 2; //今回は素因数の種類だけが分かればいい(指数は不要)
            } while (n % 2 == 0);
            // n(1 - 1/p) = n - n/pなので、 result = result - result / 2 => result -= result / 2;と等価になる
            result -= result / 2;
        }

        //ここから奇数の素数で素因数分解する
        long i = 3;

        //n / iの商が iより小さくなったらそれ以上のiでは割れないので終了
        while (i <= n / i) {
            if (n % i == 0) {
                do {
                    n /= i;
                } while (n % i == 0);
                result -= result / i;
            }
            i += 2;
        }

        //それでもnが残っていれば、それは最大の素因数
        if (n > 1) {
            result -= result / n;
        }
        return result;
    }

    /**
     * 1 から n までのオイラー関数の値を合計する
     * @param n
     * @return
     */
    private static long sumPhi(long n) {
        long result = 0;

        for (long i = 1; i <= n; i++) {
            result += phi(i);
        }
        return result;
    }

    /**
     * 牛の数を数える
     * 詳細はanswer.txt参照
     * @param n
     * @return
     */
    private static long solve(long n) {
        return sumPhi(n - 1) * 2 - 1 + 2;
    }

    public static void main(String[] args) {
        System.out.println(solve(7777777L));
    }
}