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

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?

Solution

对正整数n,欧拉函数是小于n的正整数中与n互质的数的数目。 利用[欧拉筛法](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)求欧拉函数的值。 欧拉筛保证每个合数只会被它的最小素因子筛掉,因而欧拉筛对素数的求解的复杂度是O(N)的。利用欧拉筛的想法,对每个合数将其减去所有比他小的它的最小素因子的倍数,剩下的为与其互质的数的数目,即为欧拉函数值。 代码更易于理解。

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