当前位置:首页 » Project Euler » 详细页

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

Solution

此道题目,考察了[欧拉函数](http://baike.baidu.com/link?url=bxLSlkBVlE7bUJB71hPQv6fYUzEq7GEgqAm7McohCw_0OAB3wT0zkv7gRvPS2s5WRFOk3bc92KrYfLQh2hEASWO8slbdsyHosI5WmBEun_pkHjWBUFajnQrCGESYYhDt)的相关知识。对某个正整数 $n​$,小于 $n​$ 的正整数中与 $n​$ 互质的数的数目,定义为$\phi(n)​$。这道题目: 1. 先求所有不大于$1,000,000$ 的各个正整数对应 $\phi(n)$ 2. 接着,进行一次遍历,即可得到最大的$\frac{n}{\phi(n)}$ 。遍历结束后,输出即可。 得到各个正整数$n\le1,000,000$ 的 $\phi(n)$ 值,使用如下快捷的方法: 1. 初始化数组 $totient $ ,对每个$2\le i\le1,000,000$ ,令$totient [i]=i$ 2. 对数组$totient$ ,对下标$i$, 从 $2$ 开始遍历到 $1,000,0000$。若$totient[i]=i$(即当前的遍历到的对象为质数时),对 $i$ 的倍数对应的下标 $j = 2i,3i,4i,…,ki \le1,000,000$,使$totients[j] = totients[j] - totients[j] / i$(因为正整数 $j$ 会有 $totients[j]/i$ 个整数与它不互质) 3. 遍历完 $i$ 后。数组 $totient$ 对应的各个元素 $totient[i]$,即是正整数 $i$ 对应的欧拉函数$\phi(i)​$

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;
			}
		}
		return totients;
	}
	
	
}
510510
37ms