Back to Questions
897
views1
comment
Basic isPrime alg
f#functional

I've decided to get my feet wet in functional programming for the first time w/F#, trying to teach myself to think in a different way.

I was messing around and came up with the following naive (slooow!) prime number function:

let isPrime x =
match x with
| 0 -> false
| 1 -> false
| 2 -> true
| x -> if Seq.length {for y in 2..x-1 when x % y = 0 -> y} = 0 then true else false

I was wondering how I can improve this code. Not necessarily from a strict, algorithmic standpoint, but from a more general point of view. Is that an appropriate use of the sequence composition? Could I do the same thing with lists, somehow? What might be a sensible way to handle negative numbers with this match block?This is some interesting stuff, and I'm definitely enjoying it. I wish my education hadn't completely ignored its existence. :-)

.

A better way to write this in F# would be

1
2
3

let isqrt n = n |> float |> sqrt |> int

let isPrime x = Seq.nonempty { for y in 2..isqrt x when x % y = 0 -> y } |> not

With 

1

Seq.nonempty

computation will stop after the first factor is found making the number composite, whereas with Seq.length all factors are unnecessarily computed.

The match and the especially the if were kind of unecessary too.

Using List instead of Seq would not be better in this code because since Seq is lazy the list of factors is only evaluated as needed. Whereas List is strict so even using 

1

List.nonempty

the entire list of factors is necessarily evaluated.

Oh, and I made a small algorithmic improvement of iterating to sqrt x instead of x-1.

And good luck with learning functional programming and F#!

By on 2/3/2008 7:27 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper