### Totient maximum题号：69 难度： 10 中英对照

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.

 n Relatively Prime φ(n) n/φ(n) 2 1 1 2 3 1,2 2 1.5 4 1,3 2 2 5 1,2,3,4 4 1.25 6 1,5 2 3 7 1,2,3,4,5,6 6 1.1666... 8 1,3,5,7 4 2 9 1,2,4,5,7,8 6 1.5 10 1,3,7,9 4 2.5

### Code

package projectEuler;

public final class p69 {

public static void main(String[] args) {
long start = System.nanoTime();
long result = run();
long end = System.nanoTime();
System.out.println( result );
System.out.println (( end - start )/1000000 +"ms");
}

private static final int LIMIT = (int) Math.pow(10, 6); //上限1,000,000

public static long run() {
int maxNumer = 0;
int maxDenom = 1;
int[] totients = listTotients(LIMIT);
for (int n = 1; n < totients.length; n++) {
if ((long)n * maxDenom > (long)maxNumer * totients[n]) {  //比较求最小值，这里进行了两边同乘以除数的处理，符号变成了乘号
maxNumer = n;
maxDenom = totients[n];
}
}
return maxNumer;
}

// 返回从1~n,所有的数的互质数个数
public static int[] listTotients(int n) {
if (n < 0)
throw new IllegalArgumentException("Negative array size");
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是质数时，对所有i的倍数进行处理，减去j中与其不互质的i的倍数
for (int j = i; j <= n; j += i)
totients[j] -= totients[j] / i;
}
}
}
510510
37ms