haskell 代码:如何跳过素数列表中的每隔一个数

xzv2uavs  于 2023-01-26  发布在  其他
关注(0)|答案(2)|浏览(116)

我们的目标是得到一个跳过其他素数的素数列表。一个例子是primeskip 10 --〉[2,5,11,17,23,31,41,47,59,67]。我很确定我的素数函数是有效的,但是我在跳过过程中做错了一些事情。
这是我的密码。

isPrime n = ip n [2..(n `div` 2)]
    where
    ip _ [] = True
    ip n (x:xs)
        | n `mod` x == 0 = False
        | otherwise = ip n xs

primeskip :: Int -> [Int]
primeskip n = take n [x | x <- [2,5..], isPrime x]

我试着修改filter命令,但我不知道我在做什么。我对Haskall和函数语言非常陌生。当输入primeskip 10时,我得到的结果是[2,5,11,17,23,29,41,47,53,59],在23到29之间没有正确跳过。

mcvgt66p

mcvgt66p1#

一种可能性在于单独开发:
1.一个泛型函数,跳过任何列表中的每两个元素
1.生成所有质数列表的函数
然后在最后一步把这两件事结合起来。这与工程哲学中普遍持有的观点是一致的:

  • 只做一件事,但要做好 *

对于第一步,我们可以使用递归:

everyOther :: [a] -> [a]
everyOther (x:y:zs) = x : everyOther zs
everyOther [x]      = [x]
everyOther []       = []

关于所有质数列表的计算,Haskell wiki显示了大量的可能性。
我们必须注意到,对每一个单独的数分别测试素数的方法效率非常低。利用 * 以前 * 的素数列表可以获得很多好处。例如,用非素数除候选素数是多余的。避免这些缺点的一个可能的代码如下:

-- limit the search to possible prime factors, below the square root of
-- the candidate:
getBound :: Int -> Int -> Int
getBound n b = let  b1 = b+1
               in   if (b1*b1 > n)  then  b  else  getBound n b1

findNextPrime :: Int -> Int -> Int
findNextPrime k b = if (all (\p -> mod k p /= 0) $ takeWhile (<= b) allPrimes)
                         then  k
                         else  findNextPrime (k+1) (getBound (k+1) b)

genPrimes :: Int -> Int -> [Int]
genPrimes k bound =
    let  np = findNextPrime k (getBound k bound)
    in   np : genPrimes (np+1) (getBound (np+1) bound)

allPrimes :: [Int]
allPrimes = 2 : (genPrimes 3 1)

最后,我们可以将上述两种功能结合起来:

primeSkip :: Int -> [Int]
primeSkip n = take n $ everyOther allPrimes
djp7away

djp7away2#

您希望生成 odd 整数,因为偶数根据定义不是质数,而奇数可能是也可能不是质数。

primeskip n = take n [x | x <- (2:[3,5..]), isPrime x]

但是把它放在结果前面可能会更简单,这样就可以避免测试它,因为你已经知道它是质数了。

primeskip n = 2 : (take (n-1) [x | x <- [3,5..], isPrime x])

相关问题