计算质数(F#)
2011-11-15 19:22:40| 分类：
F#
| 标签：
|举报
|字号大中小 订阅
质数，又称素数，指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数（也可定义为只有1和本身两个因数的数）。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
下面的彩图是检查120以内的所有质数。首先去掉1，因为1既不是质数也不是合数；然后2是质数，那么2的倍数都肯定不是质数了，所以把2的倍数都涂成红色（它们出局了，这里是质数的游戏...）；接下来3没有被涂掉，所以3是质数，同理把3的倍数涂成绿色；下一个未涂掉的是5，所以5也是质数，同理把5的倍数涂掉；然后再涂掉7的倍数，剩下的就都是质数了。
因“对于整数n，如果它不能被不大于n的平方根sqrt(n)的任何质数所整除，那么n就是质数”，所以这里只要检查到7即可。
求不大于n的所有质数的代码如下，作为F#练手：
// F# 2.0
// 从data中过滤掉能被kills整除的数字
let rec prime_filter kills data =
match kills with
| hd::tl -> data |> List.filter (fun x -> x % hd <> 0) |> prime_filter tl
| _ -> data
// 得到n以下所有的质数
let rec prime n =
match n with
| n when n <= 1 -> []
| _ ->
let s = n |> float |> sqrt |> int
let ps = prime s
ps @ ([(s + 1) .. n] |> prime_filter ps)
prime 120 |> printfn "%A"
输出结果为：
[2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97; 101; 103; 107; 109; 113]。
参考：
推荐：
评论这张
转发至微博
转发至微博
关闭
玩LOFTER，免费冲印20张照片，人人有奖！
我要抢>
<#--最新日志，群博日志-->
<#--推荐日志-->
<#--引用记录-->
<#--博主推荐-->
<#--随机阅读-->
<#--首页推荐-->
<#--历史上的今天-->
<#--被推荐日志-->
<#--上一篇，下一篇-->
<#-- 热度 -->
<#-- 网易新闻广告 -->
<#--右边模块结构-->
<#--评论模块结构-->
<#--引用模块结构-->
<#--博主发起的投票-->
评论