埃拉托塞尼的著名筛法
埃拉托塞尼还创造了一种筛法，称为“埃拉托塞尼筛法”：
筛法与公式的关系：
素数普遍公式：公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法：
（一）“要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可”。
（二）将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1<d≤√N”。（《基础数论》13页，U杜德利著，上海科技出版社）..
（三）再将（二）的内容等价转换：“若自然数N不能被不大于（根号）√N的任何素数整除，则N是一个素数”。见（代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页）。
（四）这句话的汉字可以等价转换成为用英文字母表达的公式：
N=p1m1+a1=p2m2+a2=......=pkmk+ak。⑴
其中 p1，p2，.....，pk表示顺序素数2，3，5，，，，，。a≠0。即N不能是2m+0，3m+0，5m+0，...，pkm+0形。若N<P（k+1）的平方 [注：后面的1，2，3，....，k，（k+1）是脚标，由于打印不出来，凡字母后面的数字或者i与k都是脚标] ，则N是一个素数。
（五）可以把⑴等价转换成为用同余式组表示：
N≡a1(modp1）， N≡a2(modp2），.....，N≡ak(modpk）。⑵
例如，29，29不能够被根号29以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。29≡1(mod2），29≡2(mod3）， 29≡4(mod5）。29小于7的平方49，所以29是一个素数。
以后平方用“*”表示，即：㎡=m*。
由于⑵的模p1，p2，....，pk 两两互素，根据孙子定理（中国剩余定理）知，⑵在p1p2.....pk范围内有唯一解。
例如k=1时，N=2m+1，解得N=3，5，7。求得了（3，3*）区间的全部素数。
k=2时，N=2m+1=3m+1，解得N=7，13，19； N=2m+1=3m+2，解得N=5，11，17，23。求得了（5，5*）区间的全部素数。
k=3时，
---------------------| 5m+1-|- 5m+2-| 5m+3,| 5m+4.|
---------------------|---------|----------|--------|---------|
n=2m+1=3m+1= |--31----|--7,37-|-13,43|--19----|
n=2m+1=3m+2= |-11,41-|-17,47-|--23---|---29---|
------------------------------------------------------------
求得了（7，7*）区间的全部素数。
仿此下去，可以求得任意大的数以内的全部素数。
