haskell - Haskell 中的汉明数

Question

我需要定义其唯一质因数为 2、3 和 5 的数字列表，即汉明数。 (即 2^i * 3^j * 5^k 形式的数字。序列以 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ... 开头)

我可以使用 factors 函数或其他方式来完成。下面的 factors 应该返回其参数的因子。我相信我已经正确实现了它。

   factors :: Int -> [Int]
   factors n = [x | x <- [1..(div n 2) ++ n], mod n x == 0]

我尝试使用列表理解来制作 2^i * 3^j * 5^k 的列表，但在编写守卫时遇到了困难:

hamming :: [Int]
hamming = [n | n <- [1..], „where n is a member of helper“]

helper :: [Int]
helper = [2^i * 3^j * 5^k | i <- [0..], j <- [0..], k <- [0..]]

Answer 1

I may do it using the factors function, or otherwise.

我建议不这样做。

一个简单的方法是实现一个函数获取一个数的质因数分解，然后你就可以有

isHamming :: Integer -> Bool
isHamming n = all (< 7) $ primeFactors n

然后将用于过滤所有正整数的列表:

hammingNumbers :: [Integer]
hammingNumbers = filter isHamming [1 .. ]

另一种更有效的方法是避免除法和过滤，并创建仅包含汉明数的列表。

一个简单的方法是利用数字n 是一个汉明数当且仅当

• n == 1，或者
• n == 2*k，其中 k 是一个汉明数，或者
• n == 3*k，其中 k 是一个汉明数，或者
• n == 5*k，其中k是一个汉明数。

然后您可以创建所有汉明数的列表作为

hammingNumbers :: [Integer]
hammingNumbers = 1 : mergeUnique (map (2*) hammingNumbers)
                                 (mergeUnique (map (3*) hammingNumbers)
                                              (map (5*) hammingNumbers))

其中 mergeUnique 将两个排序列表合并在一起，删除重复项。

这已经相当有效了，但是 it can be improved by avoiding producing duplicates from the beginning .