hamming number 题解思路#
题目：codewars网站#
solutions#
***个人第一题目思路：***就一个数的质因数分解，我只要检查这个数质因数是不是只有2 3 5就行了。#
def is_hamming_number(num):
"""判断一个数是否是 Hamming 数"""
while num % 2 == 0:
num //= 2
while num % 3 == 0:
num //= 3
while num % 5 == 0:
num //= 5
return num == 1
def generate_hamming_numbers(n):
"""生成前 n 个 Hamming 数"""
hamming_numbers = []
num = 1
while len(hamming_numbers) < n:
if is_hamming_number(num):
hamming_numbers.append(num)
num += 1
return hamming_numbers
def nth_hamming_number(n):
"""查询第 n 个 Hamming 数"""
hamming_numbers = generate_hamming_numbers(n)
return hamming_numbers[-1] if n <= len(hamming_numbers) else None简单明了的思路，就是不断遍历，直到找到质因数只有2，3，5的数，然后放进列表内。
然后，对比上面的solutions和我的思路可以发现很明显的优化，就是solutions不做多余的操作，直接找到下一个hamming number。他能做到这样，个人认为是简单分析了数字的规律，用到了一点数学分析和数论知识。以下是我的简单分析证明：
一个自己关于算法正确性的证明
这个最后我认为不可能的，是因为之前没想到，只要这个数是2 3 5的倍数就行了的。
