ProjectEuler 问题需要提示
能被 1 到 20 中所有数字整除的最小正数是多少？
我可以轻松地使用带有循环的命令式编程语言来暴力破解解决方案。但我想在 Haskell 中做到这一点，并且没有循环会让事情变得更加困难。我正在考虑做这样的事情：
[n | n <- [1..], d <- [1..20], n `mod` d == 0] !! 0
但我知道这行不通，因为“d”将使条件在 d = 1 时等于 True。我需要一个关于如何做到这一点的提示，以便 n mod d 是针对 [1..20] 计算的，并且可以对所有 20 个数字进行验证。
再次，请不要给我解决方案。谢谢。
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
I could easily brute force the solution in an imperative programming language with loops. But I want to do this in Haskell and not having loops makes it much harder. I was thinking of doing something like this:
[n | n <- [1..], d <- [1..20], n `mod` d == 0] !! 0
But I know that won't work because "d" will make the condition equal True at d = 1. I need a hint on how to make it so that n mod d is calculated for [1..20] and can be verified for all 20 numbers.
Again, please don't give me a solution. Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
与许多欧拉计划问题一样，这至少与数学和编程一样重要。
您正在寻找的是一组数字的最小公倍数，这些数字恰好位于从 1 开始的序列中。
函数式语言中的一种可能策略是尝试根据找出最小数之间的关系来使其递归能被
[1..n]整除的数，以及能被[1..n+1]整除的最小数。尝试使用一些小于 20 的数字，尝试理解数学关系或辨别某种模式。As with many of the Project Euler problems, this is at least as much about math as it is about programming.
What you're looking for is the least common multiple of a set of numbers, which happen to be in a sequence starting at 1.
A likely tactic in a functional language is trying to make it recursive based on figuring out the relation between the smallest number divisible by all of
[1..n]and the smallest number divisible by all of[1..n+1]. Play with this with some smaller numbers than 20 and try to understand the mathematical relation or perhaps discern a pattern.不要进行搜索直到找到这样的数字，而是考虑一种构造性算法，在给定一组数字的情况下，您可以构造 可被所有这些数字整除的最小（或最小）正数（又名“是其公倍数”）。查看那里的算法，并考虑如何应用欧几里得算法（他们提到的）。
你能想象两个数字之间的最大公约数和最小公倍数之间的关系吗？在一组数字中怎么样？
Instead of a search until you find such a number, consider instead a constructive algorithm, where, given a set of numbers, you construct the smallest (or least) positive number that is evenly divisible by (aka "is a common multiple of") all those numbers. Look at the algorithms there, and consider how Euclid's algorithm (which they mention) might apply.
Can you think of any relationship between two numbers in terms of their greatest common divisor and their least common multiple? How about among a set of numbers?
看了一下，好像是一个列表过滤操作。无限数字列表，根据数字是否可以被 1 到 20 之间的所有数字整除的情况进行过滤。
所以我们得到的是我们需要一个函数，它接受一个整数和一个整数列表，并告诉它是否可以被所有数字整除列表中的这些数字
，然后在列表过滤器中使用它，因为
现在 Haskell 是一种惰性语言，您只需要从上面获取所需数量的项目（在您的情况下，您只需要一个，因此 List.head 方法听起来不错）过滤结果。
我希望这对你有帮助。这是一个简单的解决方案，并且还有许多其他单行解决方案：）
If you look at it, it seems to be a list filtering operation. List of infinite numbers, to be filtered based on case the whether number is divisible by all numbers from 1 to 20.
So what we got is we need a function which takes a integer and a list of integer and tells whether it is divisible by all those numbers in the list
and then use this in List filter as
Now as Haskell is a lazy language, you just need to take the required number of items (in your case you need just one hence List.head method sounds good) from the above filter result.
I hope this helps you. This is a simple solution and there will be many other single line solutions for this too :)
替代答案：您可以利用 lcm 功能。
Alternative answer: You can just take advantage of the lcm function provided in the Prelude.
为了有效地解决这个问题，请参考 Don Roby 的答案。如果您只是想了解暴力方法的一些提示，请将您写的内容翻译回英语，看看它与问题描述有何不同。
你写了类似“过滤正自然数和从 1 到 20 的正自然数的乘积”，
你想要的更像是“通过从 1 到 20 的正自然数的某些函数过滤正自然数”
For efficiently solving this, go with Don Roby's answer. If you just want a little hint on the brute force approach, translate what you wrote back into english and see how it differs from the problem description.
You wrote something like "filter the product of the positive naturals and the positive naturals from 1 to 20"
what you want is more like "filter the positive naturals by some function of the positive naturals from 1 to 20"
在这种情况下你必须去找马西。您将通过
[1..20]执行foldl，从累加器n = 1开始。对于该列表中的每个数字p，只有当p是素数时才继续。现在，对于前一个质数p，您想要找到满足p^q <= 20的最大整数q。乘以n *= (p^q)。一旦foldl完成，n就是您想要的数字。You have to get Mathy in this case. You are gonna do a
foldlthrough[1..20], starting with an accumulatorn = 1. For each numberpof that list, you only proceed ifpis a prime. Now for the previous primep, you want to find the largest integerqsuch thatp^q <= 20. Multiplyn *= (p^q). Once thefoldlfinishes,nis the number you want.一种可能的暴力实施方式是，
但在这种情况下，它会花费太长时间。
all函数测试谓词是否适用于列表的所有元素。 lambda 是(\d -> mod nd == 0)的缩写。那么如何才能加快计算速度呢？让我们将除数分解为质因数，并搜索每个质因数的最高幂：
使用这个数字，我们得到：
嘿，它可以被 1 到 20 之间的所有数字整除。这并不奇怪。例如，它可以被 15 整除，因为它“包含”因子 3 和 5，并且它可以被 16 整除，因为它“包含”因子 2^4。但这是最小的可能数字吗？想想看...
A possible brute force implementation would be
but in this case it would take way too long. The
allfunction tests if a predicate holds for all elements of a list. The lambda is short for(\d -> mod n d == 0).So how could you speed up the calculation? Let's factorize our divisors in prime factors, and search for the highest power of every prime factor:
Using this number we have:
Hey, it is divisible by all numbers from 1 to 20. Not very surprising. E.g. it is divisible by 15 because it "contains" the factors 3 and 5, and it is divisible by 16, because it "contains" the factor 2^4. But is it the smallest possible number? Think about it...