Как провести рефакторинг кода F #, чтобы не использовать изменяемый аккумулятор?

Циклы - это хорошо, но более идиоматично - максимально абстрагироваться от циклов.

let isPrime num =
    let upperDivisor = int32(sqrt(float num))
    match num with
    | 0 | 1 -> false
    | 2 -> true
    | n -> seq { 2 .. upperDivisor } |> Seq.forall (fun x -> num % x <> 0)

let primes = Seq.initInfinite id |> Seq.filter isPrime
let nthPrime n = Seq.nth n primes

printfn "The 10001st prime number is %i." (nthPrime 10001)
printfn ""
printfn "Hit any key to continue."
System.Console.ReadKey() |> ignore

Последовательности - твой друг :)

Вы можете сослаться на мой F # для Project Euler Wiki:

Получил вот такую ​​первую версию:

let isPrime n =
    if n=1 then false
    else
        let m = int(sqrt (float(n)))
        let mutable p = true
        for i in 2..m do
            if n%i =0 then p <- false
                           // ~~ I want to break here!
        p

let rec nextPrime n =
    if isPrime n then n
    else nextPrime (n+1)

let problem7 =
    let mutable result = nextPrime 2
    for i in 2..10001 do
        result <- nextPrime (result+1)
    result

В этой версии хоть и выглядит приятнее, но я все же не преждевременно прерываю цикл, когда число не является простым. В модуле Seq методы exist и forall поддерживают раннюю остановку:

let isPrime n =
    if n<=1 then false
    else
        let m = int(sqrt (float(n)))
        {2..m} |> Seq.exists (fun i->n%i=0) |> not
        // or equivalently :
        // {2..m} |> Seq.forall (fun i->n%i<>0)

Обратите внимание, что в этой версии isPrime функция окончательно верна математически, если проверять числа ниже 2.

Или вы можете использовать хвостовую рекурсивную функцию для выполнения цикла while:

let isPrime n = 
    let m = int(sqrt (float(n)))
    let rec loop i =
        if i>m then true
        else 
            if n%i = 0 then false
            else loop (i+1)
    loop 2

Более функциональная версия задачи7 заключается в использовании Seq.unfold для генерации бесконечной последовательности простых чисел и взятия n-го элемента этой последовательности:

let problem7b =
    let primes =
        2 |> Seq.unfold (fun p ->
            let next = nextPrime (p+1) in
            Some( p, next ) )
    Seq.nth 10000 primes

Вот мое решение, в котором используется шаблон хвостовой рекурсии, который всегда позволяет избежать изменяемых параметров и получить функциональность прерывания: http://projecteulerfun.blogspot.com/2010/05/problem-7-what-is-10001st-prime-number.html

let problem7a =
    let isPrime n =
        let nsqrt = n |> float |> sqrt |> int
        let rec isPrime i =
            if i > nsqrt then true //break
            elif n % i = 0 then false //break
            //loop while neither of the above two conditions are true
            //pass your state (i+1) to the next call
            else isPrime (i+1) 
        isPrime 2

    let nthPrime n = 
        let rec nthPrime i p count =
            if count = n then p //break
            //loop while above condition not met
            //pass new values in for p and count, emulating state
            elif i |> isPrime then nthPrime (i+2) i (count+1)
            else nthPrime (i+2) p count
        nthPrime 1 1 0

    nthPrime 10001

Теперь, чтобы конкретно ответить на некоторые вопросы, которые у вас возникли в вашем решении.

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

let prime1001 = 
    let rec nthPrime i number accumulator =
        if accumulator = 1001 then number 
        //i is prime, so number becomes i in our next call and accumulator is incremented
        elif i |> isPrime then prime1001 (i+2) i (accumulator+1) 
        //i is not prime, so number and accumulator do not change, just advance i to the next odd
        else prime1001 (i+2) number accumulator
    prime1001 1 1 0

Да, есть лучший способ извлечения квадратного корня: напишите свою собственную универсальную реализацию квадратного корня (ссылка this и this post для реализации G):

///Finds the square root (integral or floating point) of n
///Does not work with BigRational
let inline sqrt_of (g:G<'a>) n =
    if g.zero = n then g.zero
    else
        let mutable s:'a = (n / g.two) + g.one
        let mutable t:'a = (s + (n / s)) / g.two
        while t < s do
            s <- t
            let step1:'a = n/s
            let step2:'a = s + step1
            t <- step2 / g.two
        s

let inline sqrtG n = sqrt_of (G_of n) n
let sqrtn = sqrt_of gn //this has suffix "n" because sqrt is not strictly integral type
let sqrtL = sqrt_of gL
let sqrtI = sqrt_of gI
let sqrtF = sqrt_of gF
let sqrtM = sqrt_of gM