我们经常跟素数打交道, 我们知道素数的各种验证算法, 但是是否存在素数的生成算法呢?
事实上, 我们有许多可以生成素数的算法, 但是, 由于这些算法的效率极低, 我们基本上不会使用这些算法.
方法一: 素数编码
设 pn 是第n个素数, Sierpinski 先生曾经定义了这样一个常量:
若定义[x]为一取下整函数, 即[x]表示不大于x的最大整数. 那么我们有:
对于这一类方法, 当把相关常量计算出来时才有实际价值, 这似乎不太可能.
方法二: 利用 Wilson 原理
Willans 先生这样定义了函数 pi(x) :
那么, 对于大于2的任意整数n, 我们有:
这个方法虽然比前一个更具体, 但是, 其中涉及到了很大的数, 要应用到实际运算中还有一定的困难.
关于素数还有很多精彩的算法, 比如验证素数的 Miller-Rabin 测试, 以及应用素数性质的 RSA 加密算法, 但有关生成素数的真正可行的算法, 还有待我们继续去探究.
Read more…
RP++
The NOI Hunan Team Selective Competition is coming…
Be confident, and then I will win! (via Byvoid)
I’ll be the one, who will make all the sorrows undone!
Pray & bless, I’ll be the one!
Struggle For HNOI 2009, Struggle For OI!
去年就开始用 Mathematica 了, 在今年 Wolfram|Alpha 推出后, 我使用 Mathematica 的次数就越来越多了, 但有时候有的函数用起来还是不够得心应手, 所以前几天特意看了一下 Overview, 把初用者需要的重点记了下来, 难免会有不准确之处, 请各位大牛批评指正.
另外, 最近一直都很忙, 有几个话题一直没写完, 所以有段时间没有更新, 望各位见谅.
Read more…
有的时候我们需求一种简介的表示数的方法，对于普通的有理数来说，普通的分数足够了。但是对于无理数，普通的分数可就无能为力了。我们有没有简介的方法来表示无理数呢？
连分数( continued fractions )就是这样的一种表示数的方法，连分数是形如下图的式子。
我们一般将连分数简写成
Read more…
World of Goo 是一个由 2D BOY 推出的大型物理学&建筑学益智游戏，这是一个有着成千上万的叫做 Goo 的粘性小球的神奇世界，该游戏的乐趣在于如何把这些 Goo 搭建到水管口处，好让更多的 Goo 被水管收集。
Read more…
WWF地球一小时 2009 – 马上加入地球一小时！
让我们都站起来，切身参与节能减排，共同应对全球气候变暖的严峻挑战，为可持续发展作出自己的贡献。