6

我写了 isPrime 函数。它检查给定的数字是否为素数。最后一个“主要”列表是单独给出的。

prime :: [Integer]
prime = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime

我认为如果可能的话，将两个函数合并为一个总是更好。所以我将 isPrime 和 prime 合并为一个函数 isPrime2。但是isPrime2的性能很差。 

isPrime2 :: Integer -> Bool
isPrime2 n | n < 2 = False
isPrime2 n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : filter isPrime2 [3..]

是素数 40000000000000000001

=> 0.5 秒

isPrime2 400000000000000000001

=> 19.8 秒

我的机器是 Ubuntu 17.10 x86-64。我正在使用 ghc 8.2.1。有谁知道为什么？

4

1 回答 1

6

第一个片段将只prime在内存中保留一个 s 列表。

第二个片段将自己计算，prime直到n^2 每次 isPrime2被调用。以前发现的素数在每次调用时都会被丢弃并重新计算。由于isPrime2是递归的，这会导致爆炸。

一种中间方法可以是这个：

isPrime2 :: Integer -> Bool
isPrime2 m = isPrime m
   where
   prime :: [Integer]
   prime = 2 : filter isPrime [3..]
   isPrime :: Integer -> Bool
   isPrime n | n < 2 = False
   isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime

这将prime在每次调用 时重新计算isPrime2，但不会导致崩溃，因为内部的每次调用都isPrime将共享相同的primes 列表。

于 2017-10-30T10:18:46.697 回答