当在F#中生成素数时，为什么会出现“色母筛"?在这个特定的实施中这么慢?

您可以避免生成除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 在我的机器上，更新的版本非常快，对于top_number = 1,000,000，它的更新时间为0.6秒.IE, What am I doing wrong here? Does it have to to with lists, sequences and arrays and the way the limitations work?So here is the setup: I'm trying to generate some primes. I see that there are a billion text files of a billion primes. The question isn't why...the question is how are the guys using python calculating all of the primes below 1,000,000 in milliseconds on this post...and what am I doing wrong with the following F# code? 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 With the timer on in FSI, I get 4.33 seconds worth of CPU for 100000... after that, it all just blows up. 解决方案 Your sieve function is slow because you tried to filter out composite numbers up to top_number. With Sieve of Eratosthenes, you only need to do so until sqrt(top_number) and remaining numbers are inherently prime. Suppose we havetop_number = 1,000,000, your function does 78498 rounds of filtering (the number of primes until 1,000,000) while the original sieve only does so 168 times (the number of primes until 1,000).You can avoid generating even numbers except 2 which cannot be prime from the beginning. Moreover, sieve and sieve_prime can be merged into a recursive function. And you could use lightweight List.filter instead of List.choose.Incorporating above suggestions: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 In my machine, the updated version is very fast and it completes within 0.6s for top_number = 1,000,000. 这篇关于当在F#中生成素数时，为什么会出现“色母筛"?在这个特定的实施中这么慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！