### 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?

### 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