Haskell素数函数不起作用

Question

我在过去的几天里开始学习Haskell，并且在这段代码中遇到了麻烦。我试图做一个函数，它会生成一个给定初始列表（至少包含2）的素数列表，最大列表长度，当前除数的索引（应该从1开始，将当前数字除以全部到目前为止的素数）和当前要测试的数字（奇数）。

我知道这不是很优雅或高效，但是这个代码不会编译或运行，所以我想在优化之前先修复它。虽然对此的建议也会很酷。

primes = [2,3,5,7,11,13] 

genPrimes primes max curDiv curTest 
    | length primes >= max = primes 
    | primes !! curDiv > floor . sqrt curTest = genPrimes (primes ++ [curTest]) max 1 (curTest + 2) 
    | curTest `mod` primes !! curDiv == 0 = genPrimes primes max 1 (curTest + 2) 
    | curTest `mod` primes !! curDiv /= 0 = genPrimes primes max (curDiv + 1) curTest 

我收到以下错误，当我尝试编译上面的代码：

Couldn't match expected type `a0 -> c0' with actual type `Integer' 
Expected type: [a0 -> c0] 
    Actual type: [Integer] 
In the first argument of `genPrimes', namely `primes' 
In the expression: genPrimes primes 50 1 15 

Answer 1

ja。已经给出了正确的答案，但是你的解决方案不是很习惯。下面是一个简单的方法来生成素数的无限名单：

primes = 2 : filter isPrime [3,5..] 

isPrime n = all ((/=0).(n `mod`)) $ takeWhile (\p -> p*p <= n) primes 

primes很容易理解，这2定义为总理，并检查所有下面的奇数，如果他们是素数。 isPrime稍微复杂一些：首先我们取所有的素数小于或等于n的平方根。然后我们检查我们是否将n除以我们没有提醒的所有这些素数等于0. isPrime指的是primes，但这不是问题，因为Haskell是懒惰的，我们从不需要“太多”素数来进行检查。

列表primes是无限的，但你可以写一些像take 10 primes。

注意，该代码有其自身的问题，请参见http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Answer 2

你已经得到了论据“：”逆转：标量转到左边，或者您也可以做一个单独的列表并连接：

| primes !! curDiv > floor . sqrt curTest = genPrimes (primes++[curTest]) max 1 curTest + 2 

Answer 3

至少，你的代码应该是

primes = [2,3,5,7,11,13] 

genPrimes primes max = go primes (length primes) 1 (last primes + 2) 
where 
    go prs len d t 
    | len >= max    = prs 
    | (prs !! d) > (floor . sqrt . fromIntegral) t 
           = go (prs++[t]) (len+1) 1 (t + 2) 
    | t `rem` (prs !! d) == 0 = go prs  len 1 (t + 2) 
    | t `rem` (prs !! d) /= 0 = go prs  len (d + 1) t 

test n = print $ genPrimes primes n 
main = test 20 

然后你重新组织这样（抽象出每个候选号码进行的测试，作为noDivs功能）：

genPrimes primes max = go primes (length primes) (last primes + 2) 
where 
    go prs len t 
    | len >= max  = prs 
    | noDivs (floor . sqrt . fromIntegral $ t) t prs 
        = go (prs++[t]) (len+1) (t + 2) 
    | otherwise  = go prs  len (t + 2) 

noDivs lim t (p:rs) 
    | p > lim   = True 
    | t `rem` p == 0 = False 
    | otherwise  = noDivs lim t rs 

那么你重写noDivs为

noDivs lim t = foldr (\p r -> p > lim || rem t p /= 0 && r) False 

然后你注意到go只是通过这样的筛选数字，通过noDivs测试：

genPrimes primes max = take max (primes ++ filter theTest [t, t+2..]) 
where 
    t = last primes + 2 
    theTest t = noDivs (floor . sqrt . fromIntegral $ t) t 

但这并没有工作，因为theTest需要通过primes（全新的素数，因为他们正在找到）到noDivs，但我们正在建设这个whole_primes列表（因为take max (primes ++ ...)），所以有一个恶性循环？不，因为我们只测试一个数字的平方根：

genPrimes primes max = take max wholePrimes 
where 
    wholePrimes = primes ++ filter theTest [t, t+2..] 
    t   = last primes + 2 
    theTest t = noDivs (floor . sqrt . fromIntegral $ t) t wholePrimes 

这是现在的工作。但最后，没有什么特殊的genPrimes现在，它只是take美化了电话，和初始primes名单实际上可以缩小，所以我们得到（改变参数安排noDivs一点，使其界面更加通用）：

primes = 2 : 3 : filter (noDivs $ tail primes) [5, 7..] 

noDivs factors t = -- return True if the supplied list of factors is too short 
    let lim = (floor . sqrt . fromIntegral $ t) 
    in foldr (\p r-> p > lim || rem t p /= 0 && r) True factors 
    -- all ((/=0).rem t) $ takeWhile (<= lim) factors 
    -- all ((/=0).rem t) $ takeWhile ((<= t).(^2)) factors 
    -- and [rem t f /= 0 | f <- takeWhile ((<= t).(^2)) factors] 

全局primes列表现在被无限期地定义（即“无限”）。 Next step是要认识到，在质数的连续平方之间，要测试的因子列表的长度将是相同的，对于每个新的分段递增1。我们可以直接生成它们的倍数（因此每一个都是从它的主要因素中生成的），而不是测试每个数字是否是它是是其平方根以下任何一个素因子的倍数。