技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 用抛物线筛选质数

用抛物线筛选质数

浏览:3576次  出处信息

     今天见到一种看上去很帅的质数筛选法。在平面直角坐标系上画出抛物线 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

建议继续学习:

  1. JavaScript实现的抛物线运动效果    (阅读:2956)
  2. 打印质数的各种算法    (阅读:2522)
  3. 用 JS 枚举质数    (阅读:1973)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1