public class Euler72 {
    public static void main(String[] args) {
        int limit = 1000000;
        int[] phi = new int[limit + 1];
        for (int i = 0; i <= limit; i++)
            phi[i] = i;
        for (int i = 2; i <= limit; i++)
            if (phi[i] == i)
                for (int j = i; j <= limit; j += i)
                    phi[j] -= phi[j] / i;
        long total = 0;
        for (int d = 2; d <= limit; d++)
            total += phi[d];
        System.out.println(total);
    }
}