学习F# - 打印素数

Question

昨天我在一些业余时间开始看F#.我想我会从打印出所有素数达到100的标准问题开始.继续我想出的......

#light
open System

let mutable divisable = false
let mutable j = 2

for i = 2 to 100 do
    j <- 2
    while j < i do
        if i % j = 0 then divisable <- true
        j <- j + 1

    if divisable = false then Console.WriteLine(i)
    divisable <- false

问题是我觉得我已经从C/C#的角度来看待这个并没有接受真正的功能语言方面.

我想知道其他人能想出什么 - 以及是否有人有任何提示/指针/建议.我感觉很好F#内容目前在网上很难获得,而我所触及的最后一种功能语言是约5年前大学时的HOPE.

Answer 1

以下是F#中Eratosthenes筛的简单实现:

let rec sieve = function
    | (p::xs) -> p :: sieve [ for x in xs do if x % p > 0 then yield x ]
    | []      -> []

let primes = sieve [2..50]
printfn "%A" primes  // [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

此实现不适用于非常大的列表,但它说明了功能解决方案的优雅.

Answer 2

简单但低效的建议：

• 创建一个函数来测试单个数字是否为素数
• 创建 2 到 100 之间的数字列表
• 按功能过滤列表
• 将结果与另一个函数组合以打印结果

为了提高效率，您确实需要通过检查一个数字是否可以被任何较小的素数整除来测试它是否为素数，这需要记忆。也许最好等到简单版本先运行:)

如果这还不够提示，请告诉我，我会想出一个完整的例子 - 我想可能要到今晚才能实现......