算区间内质数。好慢啊 T T

读了night_stalker老兄的Ruby算法求优化：spoj PRIME1，深感自己对Ruby的性能特性了解的太少了。也试了些办法不过最多也就得到了10%左右的性能提升，没啥意义。

想想，干脆用F#来试试看。这个是F# 1.9.6.2，运行环境是HP nx9040/Windows 7 Beta Build 7000。随手写了一份代码，先通过记录已知的非质数得到sqrt(n)以内的质数表ps，然后用筛选法求m..n之间的质数：

#light

let primesBetween m n =
  let pmax = int << sqrt << float <| n
  let rec loop i ps kn =
    if i > pmax then ps
    else
      let kn_next = List.fold_left (fun (acc : int Set) e -> acc.Add(e)) kn [i..i..pmax]
      loop (i + 2) (if kn.Contains(i) then ps else i :: ps) kn_next
  let ps = loop 3 [2] (Set [])
  let mm = if m <= 2 then 3 else if m % 2 = 0 then m + 1 else m
  let cand1 = List.init ((n - mm >>> 1) + 1) (fun i -> (i <<< 1) + mm)
  let cand2 = cand1 |> List.filter (fun e ->
    None = List.tryfind (fun p -> e % p = 0 && e <> p) ps)
  if m <= 2 then 2 :: cand2 else cand2

open System.Diagnostics
let watch = new Stopwatch()
watch.Start()
let primes = primesBetween 999900000 1000000000
watch.Stop()
printfn "%A" primes
printfn "%A" watch.ElapsedMilliseconds

在我的机器上运行，速度居然跟Ruby 1.9.1差不多 OTL

引用

5425L

把第8行的List.fold_left和[i..i..pmax]换成对应的Seq版，Seq.fold和{i..i..pmax}，速度只有很细微的提升。瓶颈是出在什么地方我也没弄清楚。

呜，太慢了。不过慢的主要原因应该还是我写的太糟糕了。
这种事情还是应该开多线程并行计算的好。改用比较原始的筛选法就有机会并行。以后有空再玩玩 T T