### Counting fractions题号：72 难度： 20 中英对照

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

### Code


public class p72 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
static public String run(){
long sum = 0;
final int n=1000000;
int[] totients = new int[n + 1];
for (int i = 0; i <= n; i++)
totients[i] = i;
//利用欧拉筛法计算欧拉函数值
for (int i = 2; i <= n; i++) {
if (totients[i] == i) {  // i is prime
for (int j = i; j <= n; j += i)
totients[j] -= totients[j] / i;
}
}
for (int i = 2; i < totients.length; i++)
sum += totients[i];
return Long.toString(sum);
}
}
303963552391
33ms