历史发展

古希腊

古希腊毕达哥拉斯是初等数论的先驱。他与他的学派致力于一些特殊整数（如亲和数、完全数、多边形数）及特殊不定方程的研究。公元前4世纪，欧几里德的《几何原本》通过102个命题，初步建立了整数的整除理论。他关于“素数有无穷多个”的证明，被认为是数学证明的典范。

初等数论已经有2000年的历史，公元前300年，欧几里得发现了素数是数论的基石，他自己证明了有无穷多个素数。公元前250年古希腊数学家埃拉托塞尼发明了一种筛法。2000年来，数论学的一个最重要的任务，就是寻找一个可以表示所有素数的统一公式，或者称为素数普遍公式，为此，人类耗费了巨大的心血。后来发现埃拉托塞尼筛法可以转换成为一个素数产生的公式：

公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法：

（一）“要得到不大于某个自然数n（不等于0）的所有素数，只要在2至n中将不大于的素数的倍数全部划去即可”。

（二）将上面的内容等价转换：“如果n是合数（非0自然数），则它有一个因子d满足”。1

（三）再从（二）得到等价的逆否命题：“若自然数n不能被不大于的任何素数整除，则n是一个素数”。2

（四）上述的（三）可以用符号如此表达：

N=p1m1+a1=p2m2+a2=......=pkmk+ak （1）

其中p1，p2，.....，pk顺序地表示素数2，3，5，...。a≠0。即N不能是2m+0，3m+0，5m+0，...，pkm+0形。若，则N是一个素数。

（五）可以把上述的式（1）用同余式组表示：

N≡a1(modp1）， N≡a2(modp2），.....，N≡ak(modpk）（2）

例如，29不能够被以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。

29≡1(mod2)，29≡2(mod3)， 29≡4(mod5)。29小于72=49 ，所以29是一个素数。

由于（2）的模p1，p2，....，pk两两互素，根据孙子定理（中国剩余定理）知，（2）式在p1，p2，.....，pk范围内有唯一解。

例如k=1时，N=2m+1，解得N=3，5，7。求得了（3，32）区间的全部素数。