The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?



In [63]:

    
let limit = 1000000

let compositesInRange fromNum toNum =
    [|2 .. toNum/fromNum|]
    |> Array.map (fun x -> fromNum * x)
    
let primesTo n =
    // start off assuming every number from 0 .. n is prime
    let isPrime = Array.init (1+n) (fun _ -> true)
    
    // simple sieve of eratosthenes - update "primeness" of
    // each number in the isPrime array
    for x in 2 .. int(sqrt(double(n))) do 
        if isPrime.[x] then             
            compositesInRange x n
            |> Array.map (fun i -> isPrime.[i] <- false)
            |> ignore                
    isPrime
    
let prime = primesTo limit

let rec rotate (n_list:string list) r =
    if r = 0 then []
    else
        let new_n_list = (List.tail n_list) @ [(List.head n_list)] 
       
        let new_n = 
            new_n_list
            |> String.concat ""
            |> int
    
        [ new_n_list ] @ (rotate new_n_list (r-1))
    

let rotations n = 
    let n_list = string(n).ToCharArray() |> Array.toList |> List.map string
    [ n_list ] @ (rotate n_list (n_list.Length - 1))
    
    
let allRotationsPrime n =
    rotations n 
    |> List.map (String.concat "")
    |> List.map int
    |> List.map (fun i -> prime.[i])
    |> List.fold (fun acc elem -> acc && elem) true
    

[2..limit]
|> List.filter (fun i -> prime.[i])
|> List.filter (fun n -> allRotationsPrime n)
|> List.length









    Out[63]:





55