素数懒惰序列

Question

我是F#的新手,我只是想知道是否有办法在F#中获得素数的延迟序列.

在Haskell中我使用下一个代码:

primes :: [Integer]
primes = sieve[2..]
       where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]

在F#中,我可以检查数字是否为素数:

let isPrime (number : bigint) =
    match number with
        | _ -> seq { bigint(2) .. bigint(Math.Sqrt(float number))}
        |> Seq.exists (fun x -> if (number % x = bigint(0)) then true else false)
        |> not

但我不知道如何将其转换为懒惰序列.

Answer 1

看到这个问题的答案很多,给出了F#中的延迟素数序列.

对于使用您的isPrime实现的天真解决方案(即我认为您可能有兴趣了解如何从一般的过滤器函数生成无限序列),请尝试以下方法:

let primes =
    Seq.initInfinite (fun i -> i + 2) //need to skip 0 and 1 for isPrime
    |> Seq.map (fun i -> bigint(i))
    |> Seq.filter isPrime

但是,您可能希望以不同的方式解决Project Euler Problem 3问题,方法是实现一个特定的数字因子,而不是将数字穷尽地除以质数并取最大值.虽然你最终还是需要一个素数序列生成器来解决问题.