Problem 37

Problem 37

748317

module Problem_0037

(*
3797は面白い性質を持っている.
まずそれ自身が素数であり,左から右に桁を除いたときに全て素数になっている
(3797, 797, 97, 7).
同様に右から左に桁を除いたときも全て素数である
(3797, 379, 37, 3).
右から切り詰めても左から切り詰めても素数になるような素数は11個しかない.
総和を求めよ.
注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.
*)

open System.Collections
let getprime m =
    let primes = new BitArray(m+1, true)
    seq { 0..m }
    |> Seq.filter (fun n ->
        if n < 2 then primes.[n] <- false
        elif (bigint n)*(bigint n) <= bigint m then
            if primes.[n] then
                for i in (n*n)..n..m do
                    primes.[i] <- false
        primes.[n])
    |> Seq.max |> ignore
    primes
let calc n =
  let primes = getprime 999999
  let isprime n = primes.[n]
  let d n =
    let arr = n.ToString().ToCharArray() |> Array.map(string)
    let len = arr.Length;
    [
      for p in 0..(len-2) do
        yield arr.[(p+1)..]
        yield arr.[..p]
    ] |> List.map(Array.reduce(+)>>int)
  Seq.initInfinite ((+)10)
  |> Seq.filter(isprime)
  |> Seq.filter(d>>List.forall(isprime))
  |> Seq.take n
  |> Seq.sum

let run () =
  // 条件に当てはまる素数を11個見つけた総和を求める。
  calc 11

■無限シーケンスを利用したもの（素数判定はパクリ）

let rec primes = 
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
and nextPrime n =
    if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
and isPrime n =
    if n >= 2 then
        primes
        |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
        |> fun x -> x.Value * x.Value > n
    else false
let calc n =
  let d n =
    let arr = n.ToString().ToCharArray() |> Array.map(string)
    let len = arr.Length;
    [
      for p in 0..(len-2) do
        yield arr.[(p+1)..]
        yield arr.[..p]
    ] |> List.map(Array.reduce(+)>>int)
  Seq.initInfinite ((+)10)
  |> Seq.filter(isPrime)
  |> Seq.filter(d>>List.forall(isPrime))
  |> Seq.take n
  |> Seq.max

■参考サイト
無限シーケンス素数

• • -