埃拉托斯特尼筛法
維基百科,自由的 encyclopedia
埃拉托斯特尼筛法(古希臘語:κόσκινον Ἐρατοσθένους,英語:sieve of Eratosthenes),簡稱埃氏筛,是一种用來生成(英语:Generating primes)質數的筛法,得名於古希臘數學家埃拉托斯特尼。其基本步骤是從最小的質數2開始,將该質數的所有倍數標記成合數,而下一个尚未被标记的最小自然数3即是下一个質數。如此重复这一过程,将各个质数的倍数标记为合数并找出下一个质数,最终便可找出一定範圍內所有質數。
埃拉托斯特尼筛法可能在埃拉托斯特尼的时代之前就已经为人所知[1]:14,并记载于另一位古希腊数学家尼科马库斯的《算术概论(英语:Introduction to Arithmetic)》中,尽管该著作中的这一筛法是从3开始,从奇数中依次筛去奇数的倍数,而非从自然数中筛去质数的倍数[2]:242-243。