Функция Томаса Петричека довольно быстрая, но мы можем сделать это немного быстрее.
Сравните следующее:
let is_prime_tomas n =
let ms = int64(sqrt(float(n)))
let rec isPrimeUtil(m) =
if m > ms then true
elif n % m = 0L then false
else isPrimeUtil(m + 1L)
(n > 1L) && isPrimeUtil(2L)
let is_prime_juliet n =
let maxFactor = int64(sqrt(float n))
let rec loop testPrime tog =
if testPrime > maxFactor then true
elif n % testPrime = 0L then false
else loop (testPrime + tog) (6L - tog)
if n = 2L || n = 3L || n = 5L then true
elif n <= 1L || n % 2L = 0L || n % 3L = 0L || n % 5L = 0L then false
else loop 7L 4L
is_prime_juliet имеет немного более быстрый внутренний цикл. Это хорошо известная стратегия генерации простых чисел, которая использует «переключение» для пропуска не простых чисел с шагом 2 или 4. Для сравнения:
> seq { 2L .. 2000000L } |> Seq.filter is_prime_tomas |> Seq.fold (fun acc _ -> acc + 1) 0;;
Real: 00:00:03.628, CPU: 00:00:03.588, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 148933
> seq { 2L .. 2000000L } |> Seq.filter is_prime_juliet |> Seq.fold (fun acc _ -> acc + 1) 0;;
Real: 00:00:01.530, CPU: 00:00:01.513, GC gen0: 0, gen1: 0, gen2: 0
val it : int = 148933
Моя версия примерно в 2,37 раза быстрее, и она также довольно близка к скорости самых быстрых императивных версий. Мы можем сделать это еще быстрее , потому что нам не нужно фильтровать список 2L .. 2000000L, мы можем использовать ту же стратегию для генерации более оптимальной последовательности возможных простых чисел, прежде чем применять наш фильтр:
> let getPrimes upTo =
seq {
yield 2L;
yield 3L;
yield 5L;
yield! (7L, 4L) |> Seq.unfold (fun (p, tog) -> if p <= upTo then Some(p, (p + tog, 6L - tog)) else None)
}
|> Seq.filter is_prime_juliet;;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val getPrimes : int64 -> seq<int64>
> getPrimes 2000000L |> Seq.fold (fun acc _ -> acc + 1) 0;;
Real: 00:00:01.364, CPU: 00:00:01.357, GC gen0: 36, gen1: 1, gen2: 0
val it : int = 148933
Мы упали с 1,530 до 01,364 с, поэтому мы увеличили скорость примерно на 1,21 раза. Удивительный!