Можно ли улучшить время выполнения этого генератора простых чисел?
Моей первоначальной целью при написании этого было оставить как можно меньше места. Я могу с уверенностью сказать, что эта цель была достигнута. К сожалению, это оставляет меня с довольно медленной реализацией. Для генерации всех простых чисел менее 2 миллионов требуется около 8 секунд на чипе Intel с частотой 3 ГГц.
Есть ли способ улучшить время выполнения этого кода с минимальным ущербом для небольшого объема памяти? Или я поступаю неправильно, если смотреть на это с функциональной точки зрения?
КОД
/// 6.5s for max = 2,000,000
let generatePrimeNumbers max =
let rec generate number numberSequence =
if number * number > max then numberSequence else
let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L)
let newNumberSequence = seq { for i in filteredNumbers -> i }
let newNumber = newNumberSequence |> Seq.find (fun x -> x > number)
generate newNumber newNumberSequence
generate 2L (seq { for i in 2L..max -> i })
Обновить
Я настроил алгоритм и сумел сбрить 2 секунды, но удвоил потребление памяти.
/// 5.2s for max = 2,000,000
let generatePrimeNumbers max =
let rec generate number numberSequence =
if number * number > max then numberSequence else
let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L) |> Seq.toArray |> Array.toSeq
let newNumber = filteredNumbers |> Seq.find (fun v -> v > number)
generate newNumber filteredNumbers
generate 2L (seq { for i in 2L..max -> i })
Обновить
Видимо, я использовал старый компилятор. В последней версии мой оригинальный алгоритм занимает 6,5 с, а не 8 с. Это довольно улучшение.