以图明志

计算机算法

SICP:费马小定理与素数检测

费马小定理是数论的基础理论之一
我知道费马等一些人都热衷于“纯数学”,那些被看起来毫无实用价值的“纯理论”,可这费马检查,却是全世界的服务器每秒中都要运行无数次的 RSA 算法的理论基石。就我自己而言,每天使用 SSH 的时候都要用到。而几位科学家把这这一切联系起来的过程,实在称得上是“玄妙”了。

计算机算法

如何提高筛选法求大范围素数的效率

学习一下这种求素数的算法
筛选法求素数有一个很通用的算法,就是在遍例该集合时,比方检验一个数N是否素数,用N除以2-N的开方,只要有一个能整除,就说明N不是素数。另外这道题要求用数组来计算。谓"筛选法"指的是"埃拉托色尼(Eratosthenes)筛法"。他是古希腊的著名数学家。

计算机算法

哥德巴赫猜想的程序验证

任何一个充分大的偶数都可以表示为两个素数之和
Timus Online Judge 网站上有这么一道题目:1356. Something Easier。这道题目的输入是一组 2 到 109 之间整数,对于每个输入的整数,要求用最少个数的素数的和来表示。这道题目的时间限制是 1 秒。我们知道著名的哥德巴赫猜想是:任何一个充分大的偶数都可以表示为两个素数之和。
1 / 1 首页 < Prev 1 Next > 尾页 页码: