Monday, June 14, 2010

Problem 35: How many circular primes are there below one million?

Now we get to use our Digits module.  The most interesting part of this algorithm is performing digit rotations (the assignment of r), which went through several revisions before I got it just right.

let problem35c = 
    let isCircularPrime n =
        if not (isPrime n) then false
        else 
            let digs = n |> Digits.fromInt
            let rec loop i = 
                if i = (Seq.length digs)-1 then true
                else
                    let i = i + 1
                    let r = //rotate by i
                        Seq.append 
                            (digs |> Seq.skip i) 
                            (digs |> Seq.take i)
                        |> Digits.toInt
                    if isPrime r then loop i
                    else
                        false
            loop 0

    //we are given that there are 13 such primes below 100
    ({101..2..999999}
    |> Seq.filter isCircularPrime
    |> Seq.length) + 13

No comments:

Post a Comment