当在F#中生成Primes时,为什么"Erosthenes的筛子"在这个特定的实现中如此缓慢？

Question

IE浏览器,

我在这做错了什么？是否必须使用列表,序列和数组以及限制的工作方式？

所以这是设置:我正在尝试生成一些素数.我看到有十亿个素数的十亿个文本文件.问题不是为什么......问题是这些人如何在这篇文章中使用python计算1,000,000毫秒以下的所有素数......以及我对以下F#代码做错了什么？

let sieve_primes2 top_number = 
    let numbers = [ for i in 2 .. top_number do yield i ]
    let sieve (n:int list) = 
        match n with
        | [x] -> x,[]
        | hd :: tl -> hd, List.choose(fun x -> if x%hd = 0 then None else Some(x)) tl
        | _ -> failwith "Pernicious list error."
    let rec sieve_prime (p:int list) (n:int list) =  
        match (sieve n) with
        | i,[] -> i::p
        | i,n'  -> sieve_prime (i::p) n'
    sieve_prime [1;0] numbers 

随着FSI中的计时器开启,我获得了价值4.33秒的CPU 100000 ...之后,它就会爆炸.

Answer 1

您的筛选功能很慢,因为您尝试过滤掉最多的复合数字top_number.使用Eratosthenes的Sieve,你只需要这样做,直到sqrt(top_number)剩下的数字本来就是素数.假设我们有top_number = 1,000,000,你的函数进行78498几轮过滤(质数的数量直到1,000,000),而原始筛只进行这样的168次数(质数的数量直到1,000).

除了2之外,你可以避免生成偶数,这些数字从一开始就不是素数.此外,sieve和sieve_prime可以合并成一个递归函数.你可以使用轻量级List.filter而不是List.choose.

纳入以上建议:

let sieve_primes top_number = 
    let numbers = [ yield 2
                    for i in 3..2..top_number -> i ]
    let rec sieve ns = 
        match ns with
        | [] -> []
        | x::xs when x*x > top_number -> ns
        | x::xs -> x::sieve (List.filter(fun y -> y%x <> 0) xs)
    sieve numbers 

在我的机器中,更新版本非常快,并且在0.6秒内完成top_number = 1,000,000.