Just because I'm bored, I wrote yet another prime number generator. I think it's pretty clean, but I won't be surprised if someone finds something to comment on.

let isPrime (knownPrimes :int list) currentNumber =
    List.forall (fun i -> currentNumber % i <> 0) knownPrimes

let rec primes knownPrimes currentNumber =
    match isPrime knownPrimes currentNumber with
    | true ->

        primes (currentNumber::knownPrimes) (currentNumber + 2)
    | false -> primes knownPrimes (currentNumber + 2)

let main argv =
    primes [2] 3 |> ignore

Writing something consecutively to the console is of very little value. OK, primes returns a list of primes, but you really can't use them until all primes are calculated in the domain of int, and that's a lot.

For instance, it is useless to write

primes [2] 3  |> Seq.take 10 |> Seq.iter (printfn "%i")

because it will not return before all primes are calculated.

It is btw strange that the client of the primes has to figure out that 2 is a prime :-): primes [2] 3 |> ignore

You could change the function to take a max or a count value to stop the generator when enough is enough.

As an alternative it is IMO more useful to return a Seq of primes, because it returns the primes as soon as they are individually calculated:

let enumPrimes = 
    let rec primes currentNumber knownPrimes =
        match isPrime currentNumber knownPrimes with
        | true -> 
            seq { 
                yield currentNumber 
                yield! (primes (currentNumber + 2) (currentNumber::knownPrimes))
        | false -> primes (currentNumber + 2) knownPrimes 

    seq {
        yield 2
        yield! [2] |> primes 3 

When determine if a number is a prime, it is only necessary to check primes up to (inclusive) the square root of the number:

let isPrime currentNumber knownPrimes =
    let sqrtNum = sqrt (float currentNumber) |> int
    knownPrimes |> List.rev |> List.takeWhile (fun p -> p <= sqrtNum) |> List.tryFind (fun p -> currentNumber % p = 0) = None

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.