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

Generalised Hamming Numbers 题号:204 难度: 30 中英对照

A Hamming number is a positive number which has no prime factor larger than 5.
So the first few Hamming numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.
There are 1105 Hamming numbers not exceeding 108.

We will call a positive number a generalised Hamming number of type n, if it has no prime factor larger than n.
Hence the Hamming numbers are the generalised Hamming numbers of type 5.

How many generalised Hamming numbers of type 100 are there which don't exceed 109?

Solution

考虑限度在$i$以内,前$j$个素数组成的汉明数个数为$H(i,j)$ 这些汉明数包含两部分,一部分是含有素因子$prime[j]$,这一部分的计算将$i$除以$prime[j]$后将答案加上$H(i,j-1)$即可,考虑到素因子的次数可能更高,所以只要$i/prime[j]>0$就可以将$i$不断除以$prime[j]$,并将答案不断加上$H(i,j-1)$即可;另一部分不含素因子,此时直接将$H(i,j-1)$加到答案上即可。 考虑到边界情况$H(i,0)$,不包含其他素数的汉明数个数,可以直接由$\left[log_2(i)\right]+1$,其中$\left[ x\right]$表示高斯取整函数。

Code

public final class p204 {
    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 int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
			47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 };

    static public String run() {
    	return ""+hamming(1000000000, primes.length - 1);
	}

	private static int hamming(int i, int j) {
		if (j == 0)
			return (int) (Math.log(i) / Math.log(2)) + 1;
		else {
			int result = 0;
			while (i > 0) {
				result += hamming(i, j - 1);
				i /= primes[j];
			}
			return result;
		}
	}


}
2944730
79ms