Haskell -列表理解

nkkqxpd9  于 2023-04-12  发布在  其他
关注(0)|答案(2)|浏览(130)

我的练习是定义一个函数,它返回一个在给定区间内至少有三位数的素数列表。
例如,在这种情况下,它必须返回primeNumbers 100 200 = [101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]。
这是我的代码

primesNumbers :: Int -> Int -> [Int]
primesNumbers a b = [n | n <- [a..b], n > 99, all (\x -> n `mod` x /= 0) [x | x <- [2.. max a b]]]

但是在这个例子中,质数100 200,它只返回[]。
有什么问题吗?

6fe3ivhb

6fe3ivhb1#

问题

首先,让我注意一个事实,n > 99可能是不需要的。如果a大于100,n不能小于99。要么你想要所有的素数大于99,要么你做了一些错误。所以我将没有它。
如果我们分解你的代码,就有可能写出

primesNumbers :: Int -> Int -> [Int]
primesNumbers a b = [n | n <- [a..b], f a b n]

f :: Int -> Int -> Int -> Bool
f a b n = all (\x -> n `mod` x /= 0) [x | x <- [2.. max a b]]

如果我们想为f提供一个更好的名字,我们可以查看代码,它试图测试2和max a b之间的所有数字是否都是n的除数。因此,让我们将f称为函数can_be_divided_by_a_number_between_a_and_b
所以你现在的功能是

primesNumbers a b = [n | n <- [a..b], can_be_divided_by_a_number_between_a_and_b a b n]

当你调用primeNumbers 100 200时,你想找出100到200之间所有不能被2到200之间的数字整除的数字n。现在,101是一个相关的选择吗?不,因为显然101可以被100到200之间的数字整除......它可以被自己整除。

解决方案

现在你可以看到这不是你想要的,你的上限太高了,你想找到一种方法来表达它不能被严格介于1和它本身之间的数字整除,即Haskell中的 ]1,n[[2 .. n-1]
让我们找到一种方法来写cant_be_divided_by_a_number_stritly_between_2_and_itself。为了简洁起见,我将其称为is_prime,因为这是它的定义。

is_prime :: Int -> Bool
is_prime n = all (\x -> n `mod` x /= 0) [x | x <- [2 .. n-1]]

现在很容易写你的函数。因为你想要所有的素数之间的ab,它是

primeNumbers a b = [n | n <- [a..b], is_prime n]
  • 结论 *

依我拙见,你应该从后者开始...写作

primeNumbers a b = [n | n <- [a..b], is_prime n]

是自上而下方法的开始,它帮助您将问题分解为更小的问题,并逐步提供解决方案。编写下一步is_prime n比尝试一步解决所有问题要容易得多。
您可以看到,它可以很容易地推广到所有可能的 predicate p

verify_p_between_a_and_b p a b = = [n | n <- [a..b], p n]

所以呢

primesNumbers = verify_p_between_a_and_b is_prime

:)

yyyllmsg

yyyllmsg2#

您正在检查:

all (\x -> n `mod` x /= 0) [x | x <- [2.. max a b]]

这意味着例如5,它是素数,最终它会产生x = 5,并且一个数总是可以被它自己整除。
你的主检查器只是检查它是否可以被大于或等于2的任何数整除,每个大于或等于2的数都具有该属性:它可被自身分割。
您应该通过以下方式提高检查器的效率:

primesNumbers :: Int -> Int -> [Int]
primesNumbers a b = [n | n <- [max 100 a .. b], all (\x -> n `mod` x /= 0) (2:[3, 5 .. n-1])]

但是我们可以更有效地做这件事,事实上,我们只需要检查直到 √n,所以我们可以更早地停止搜索,我们也不需要检查前一个素数 p 的任何倍数,事实上,如果没有更小的素数 q,对于任何 n∈ N 0p=(n+q)×q,那么检查一个数 p 是否是素数就足够了,我把它作为一个练习。

相关问题