用抛物线筛选质数
浏览:3634次 出处信息
今天见到一种看上去很帅的质数筛选法。在平面直角坐标系上画出抛物线 y = x2 的图像，然后标出抛物线上的所有格点(两坐标均为整数的点)。其中，只有点 (0, 0) 正好在 y 轴上，其余的点要么在 y 轴左侧，要么在 y 轴右侧。把 y 轴左侧除了 (-1, 1) 以外的所有格点与 y 轴右侧除了 (1, 1) 以外的所有格点相连，这些连线将自动避开 y 轴上纵坐标为质数的点。连接足够多的线条之后，质数就逐渐露了出来。
这是因为， (-a, a2) 和 (b, b2) 的连线将经过 (0, a ・ b) ，这可以通过计算斜率的方法得到验证。这个颇具创意的质数筛选法叫做 visual sieve ，它是由 Yuri Matiyasevich 和 Boris Stechkin 提出的。
查看更多：
http://plus.maths.org/content/catching-primes
建议继续学习：
QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习
扫一扫订阅我的微信号：IT技术博客大学习
<< 前一篇：趣题：只用一把带有两条平行边的直尺作图
后一篇：基于C++ Lambda表达式的程序优化 >>
文章信息
- 作者：Matrix67 来源： Matrix67: My Blog
- 标签： 抛物线 质数
- 发布时间：2011-11-06 22:32:03
近3天十大热文
-
[82] memory prefetch浅析 -
[53] 转载：cassandra读写性能原理分析
-
[51] 深入浅出cassandra 4 数据一致性问
-
[51] 基本排序算法的PHP实现
-
[46] 字符引用和空白字符
-
[42] Inline Form Labels
-
[41] 获取Dom元素的X/Y坐标
-
[41] MySQL半同步存在的问题
-
[40] javascript插入样式
-
[40] JS中如何判断字符串类型的数字
