注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

秒大刀 博客

好好学习 天天向上

 
 
 

日志

 
 
 
 

计算质数(F#)  

2011-11-15 19:22:40|  分类: F# |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    质数,又称素数,指在一个大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数)。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着很重要的地位。
    埃拉托斯特尼筛法,简称埃氏筛或爱氏筛,是一种公元前250年由古希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。
    下面的彩图是检查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]。

参考:

推荐:
  评论这张
 
阅读(900)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017