题目204：广义汉明数

欧拉计划

Generalised Hamming Numbers

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 10⁸.

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 10⁹?

题目：

汉明数是没有大于 5 的质因子的正整数。
所以，前几个汉明数分别是 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15。

在比 10⁸ 小的数字中，有 1105 个汉明数。

我们把没有大于 n 的质因子的数叫做 n 类型的广义汉明数。
所以，标准的汉明数是类型为 5 的汉明数。

请问在 10⁹ 以内（包含），类型 100 的汉明数有多少个？

jerryxjr1220

def hamming(n):
        base = [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]
        hamm = [1]
        for i in base:
                for j in hamm:
                        if i*j<=n:
                                hamm.append(i*j)
        return len(hamm)
print(hamming(10**9))

2944730
[Finished in 2.1s]