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