我是纯功能F＃兴趣埃拉托色尼的筛的实现。我感兴趣的实际筛的实现，不是天真功能的实现，是不是真的筛，所以没有这样的事情：

I am interested in an implementation of the sieve of eratosthenes in purely functional F#. I am interested in an implementation of the actual sieve, not the naive functional implementation that isn't really the sieve, so not something like this:

let rec PseudoSieve list =
    match list with
    | hd::tl -> hd :: (PseudoSieve <| List.filter (fun x -> x % hd <> 0) tl)
    | [] -> []

以上简要的第二个链接描述了一个算法，将需要使用一个多重映射，这是不是可以在F＃据我知道。 Haskell的实施给使用支持的 insertWith 方法，我还没有看到可供的 F＃的功能地图。

The second link above briefly describes an algorithm that would require the use of a multimap, which isn't available in F# as far as I know. The Haskell implementation given uses a map that supports an insertWith method, which I haven't seen available in the F# functional map.

有谁知道一个办法把给定的哈斯克尔地图code至F＃，或许知道的另一种实现方法或筛分算法是高效和更适合于功能的实现或F＃？

Does anyone know a way to translate the given Haskell map code to F#, or perhaps knows of alternative implementation methods or sieving algorithms that are as efficient and better suited for a functional implementation or F#?

推荐答案

阅读这篇文章，我想出了不需要multimap中的想法。它处理由连连移动通过其首要值碰撞键向前，直到它到达一个关键是在地图上不碰撞映射键。在素数是下一个迭代值的键，而且是素数的值的地图。

Reading that article I came up with an idea that doesn't require a multimap. It handles colliding map keys by moving the colliding key forward by its prime value again and again until it reaches a key that isn't in the map. Below primes is a map with keys of the next iterator value and values that are primes.

let primes = 
    let rec nextPrime n p primes =
        if primes |> Map.containsKey n then
            nextPrime (n + p) p primes
        else
            primes.Add(n, p)

    let rec prime n primes =
        seq {
            if primes |> Map.containsKey n then
                let p = primes.Item n
                yield! prime (n + 1) (nextPrime (n + p) p (primes.Remove n))
            else
                yield n
                yield! prime (n + 1) (primes.Add(n * n, n))
        }

    prime 2 Map.empty

我终于想通了，从纸最终优先级队列的算法。 I $低于p $ psent它。我把通用优先级队列功能在顶部。我用一个元组重新present懒列表迭代。该算法达到整数溢出比上面的算法，这是一件好事，因为这意味着我们跳过多个测试用例更快。

I finally figured out the final priority queue based algorithm from that paper. I present it below. I placed the generic priority queue functions at the top. I use a tuple to represent the lazy list iterators. This algorithm reaches integer overflow faster than the above algorithm which is a good thing since it means we are skipping more test cases.

let primes = 
    // the priority queue functions
    let insert = SkewBinomialHeap.insert
    let findMin = SkewBinomialHeap.findMin
    let insertDeleteMin value = SkewBinomialHeap.deleteMin >> SkewBinomialHeap.insert value
    let empty = []


    let wheelData = [|2L;4L;2L;4L;6L;2L;6L;4L;2L;4L;6L;6L;2L;6L;4L;2L;6L;4L;6L;8L;4L;2L;4L;2L;4L;8L;6L;4L;6L;2L;4L;6L;2L;6L;6L;4L;2L;4L;6L;2L;6L;4L;2L;4L;2L;10L;2L;10L|]

    // increments iterator
    let wheel (composite, n, multiple) =
        composite + wheelData.[n % 48] * multiple, n + 1, multiple

    let insertPrime (prime, n, multiple) table =
        insert (prime * prime, n, multiple * prime) table

    let rec adjust x table =
        let composite, n, multiple = findMin table

        if composite <= x then 
            table 
            |> insertDeleteMin (wheel (composite, n, multiple))
            |> adjust x
        else
            table

    let rec sieve iterator table =
        seq {
            let x, _, _ = iterator
            let composite, _, _ = findMin table

            if composite <= x then
                yield! sieve (wheel iterator) (adjust x table)
            else
                yield x
                yield! sieve (wheel iterator) (insertPrime iterator table)
        }

    sieve (13L, 1, 1L) (insertPrime (11L, 0, 1L) empty)
    |> Seq.append [2L;3L;5L;7L;11L]