Обучение F # - печать простых чисел

Ответ 1

Вот простая реализация Сито Эратосфена в F #:

let rec sieve = function
    | (p::xs) -> p :: sieve [ for x in xs do if x % p > 0 then yield x ]
    | []      -> []

let primes = sieve [2..50]
printfn "%A" primes  // [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

Эта реализация не будет работать для очень больших списков, но она иллюстрирует элегантность функционального решения.

Ответ 2

Использование ситовой функции, такой как Eratosthenes, - хороший способ. Функциональные языки очень хорошо работают со списками, поэтому я бы начал с этого делать для struture.

В другой заметке функциональные языки хорошо работают из функций (хех). Для функционального языка "чувствовать" я бы построил функцию сита, а затем позвонил ему, чтобы распечатать простые числа. Вы могли бы даже разделить его: одна функция строит список и выполняет всю работу, а другая проходит и выполняет всю печать, аккуратно разделяющую функциональность.

Здесь есть несколько интересных версий здесь. И есть хорошо известные реализации на других подобных языках. Здесь один в OCAML, который превосходит один в C.

Ответ 3

Вы определенно не хотите учиться на этом примере, но я написал реализацию F # сит NewSqueak на основе передачи сообщения:

type 'a seqMsg =   
    | Die   
    | Next of AsyncReplyChannel<'a>   

type primes() =   
    let counter(init) =   
        MailboxProcessor.Start(fun inbox ->   
            let rec loop n =   
                async { let! msg = inbox.Receive()   
                        match msg with   
                        | Die -> return ()   
                        | Next(reply) ->   
                            reply.Reply(n)   
                            return! loop(n + 1) }   
            loop init)   

    let filter(c : MailboxProcessor<'a seqMsg>, pred) =   
        MailboxProcessor.Start(fun inbox ->   
            let rec loop() =   
                async {   
                    let! msg = inbox.Receive()   
                    match msg with   
                    | Die ->   
                        c.Post(Die)   
                        return()   
                    | Next(reply) ->   
                        let rec filter' n =   
                            if pred n then async { return n }   
                            else  
                                async {let! m = c.AsyncPostAndReply(Next)   
                                       return! filter' m }   
                        let! testItem = c.AsyncPostAndReply(Next)   
                        let! filteredItem = filter' testItem   
                        reply.Reply(filteredItem)   
                        return! loop()   
                }   
            loop()   
        )   

    let processor = MailboxProcessor.Start(fun inbox ->   
        let rec loop (oldFilter : MailboxProcessor<int seqMsg>) prime =   
            async {   
                let! msg = inbox.Receive()   
                match msg with   
                | Die ->   
                    oldFilter.Post(Die)   
                    return()   
                | Next(reply) ->   
                    reply.Reply(prime)   
                    let newFilter = filter(oldFilter, (fun x -> x % prime <> 0))   
                    let! newPrime = oldFilter.AsyncPostAndReply(Next)   
                    return! loop newFilter newPrime   
            }   
        loop (counter(3)) 2)   

    member this.Next() = processor.PostAndReply( (fun reply -> Next(reply)), timeout = 2000)

    interface System.IDisposable with
        member this.Dispose() = processor.Post(Die)

    static member upto max =   
        [ use p = new primes()
          let lastPrime = ref (p.Next())
          while !lastPrime <= max do
            yield !lastPrime
            lastPrime := p.Next() ]

Работает ли он?

> let p = new primes();;

val p : primes

> p.Next();;
val it : int = 2
> p.Next();;
val it : int = 3
> p.Next();;
val it : int = 5
> p.Next();;
val it : int = 7
> p.Next();;
val it : int = 11
> p.Next();;
val it : int = 13
> p.Next();;
val it : int = 17
> primes.upto 100;;
val it : int list
= [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71;
   73; 79; 83; 89; 97]

Сладкое!:)

Ответ 4

Вот мои два цента:

let rec primes = 
  seq { 
    yield 2
    yield! (Seq.unfold (fun i -> Some(i, i + 2)) 3) 
           |> Seq.filter (fun p -> 
                primes
                |> Seq.takeWhile (fun i -> i * i <= p)
                |> Seq.forall (fun i -> p % i <> 0))
  }
  for i in primes do
    printf "%d " i

Или, может быть, эта более ясная версия того же самого, что и isprime, определяется как отдельная функция:

let rec isprime x =
    primes
    |> Seq.takeWhile (fun i -> i*i <= x)
    |> Seq.forall (fun i -> x%i <> 0)

and primes = 
    seq {
        yield 2
        yield! (Seq.unfold (fun i -> Some(i,i+2)) 3)
                |> Seq.filter isprime
    }

Ответ 5

Простое, но неэффективное предложение:

• Создайте функцию, чтобы проверить, является ли одно число простым
• Создайте список для чисел от 2 до 100
• Отфильтровать список по функции
• Составьте результат с другой функцией, чтобы распечатать результаты

Чтобы сделать это эффективным, вы действительно хотите проверить, является ли число простым, проверяя, делится ли оно на какие-либо более низкие простые числа, что потребует memoisation. Наверное, лучше подождать, пока у вас будет простая версия, работающая сначала:)

Сообщите мне, если этого недостаточно, и я придумаю полный пример - подумал, что может быть не до сегодняшнего дня...

Ответ 6

Вот мой старый пост в HubFS об использовании рекурсивного seq для реализации генератора простых чисел.

Для случая, когда вам нужна быстрая реализация, есть отличный код OCaml от Markus Mottl

P.S. если вы хотите итерировать простое число до 10 ^ 20, вы действительно хотите передать prgengen D. D. Bernstein в F #/OCaml:)

Ответ 7

При решении той же проблемы я внедрил Сито Аткинса в F #. Это один из самых эффективных современных алгоритмов.

// Create sieve
let initSieve topCandidate =
    let result = Array.zeroCreate<bool> (topCandidate + 1)
    Array.set result 2 true
    Array.set result 3 true
    Array.set result 5 true
    result
// Remove squares of primes
let removeSquares sieve topCandidate =
    let squares =
        seq { 7 .. topCandidate}
            |> Seq.filter (fun n -> Array.get sieve n)
            |> Seq.map (fun n -> n * n)
            |> Seq.takeWhile (fun n -> n <= topCandidate)
    for n2 in squares do
        n2
            |> Seq.unfold (fun state -> Some(state, state + n2))
            |> Seq.takeWhile (fun x -> x <= topCandidate)
            |> Seq.iter (fun x -> Array.set sieve x false)
    sieve

// Pick the primes and return as an Array
let pickPrimes sieve =
    sieve
        |> Array.mapi (fun i t -> if t then Some i else None)
        |> Array.choose (fun t -> t)
// Flip solutions of the first equation
let doFirst sieve topCandidate =
    let set1 = Set.ofList [1; 13; 17; 29; 37; 41; 49; 53]
    let mutable x = 1
    let mutable y = 1
    let mutable go = true
    let mutable x2 = 4 * x * x
    while go do
        let n = x2 + y*y
        if n <= topCandidate then
            if Set.contains (n % 60) set1 then
                Array.get sieve n |> not |> Array.set sieve n

            y <- y + 2
        else
            y <- 1
            x <- x + 1
            x2 <- 4 * x * x
            if topCandidate < x2 + 1 then
                go <- false
// Flip solutions of the second equation
let doSecond sieve topCandidate =
    let set2 = Set.ofList [7; 19; 31; 43]
    let mutable x = 1
    let mutable y = 2
    let mutable go = true
    let mutable x2 = 3 * x * x
    while go do
        let n = x2 + y*y
        if n <= topCandidate then
            if Set.contains (n % 60) set2 then
                Array.get sieve n |> not |> Array.set sieve n

            y <- y + 2
        else
            y <- 2
            x <- x + 2
            x2 <- 3 * x * x
            if topCandidate < x2 + 4 then
                go <- false
// Flip solutions of the third equation
let doThird sieve topCandidate =
    let set3 = Set.ofList [11; 23; 47; 59]
    let mutable x = 2
    let mutable y = x - 1
    let mutable go = true
    let mutable x2 = 3 * x * x
    while go do
        let n = x2 - y*y
        if n <= topCandidate && 0 < y then
            if Set.contains (n % 60) set3 then
                Array.get sieve n |> not |> Array.set sieve n

            y <- y - 2
        else
            x <- x + 1
            y <- x - 1
            x2 <- 3 * x * x
            if topCandidate < x2 - y*y then
                go <- false

// Sieve of Atkin
let ListAtkin (topCandidate : int) =
    let sieve = initSieve topCandidate

    [async { doFirst sieve topCandidate }
     async { doSecond sieve topCandidate }
     async { doThird sieve topCandidate }]
        |> Async.Parallel
        |> Async.RunSynchronously
        |> ignore

    removeSquares sieve topCandidate |> pickPrimes

Я знаю, что некоторые не рекомендуют использовать Parallel Async, но он увеличил скорость ~ 20% на моем 2-ядерном (4 с гиперпотоком) i5. Что примерно такое же увеличение я получил с помощью TPL.

Я пробовал переписывать его по-функциональному, считывая циклы и изменяемые переменные, но производительность снижалась в 3-4 раза, поэтому решила сохранить эту версию.