Eratoschenes篩法

Eratoschenes篩法是一種尋找不可約數（素數）的方法。

為了求出不超過N（N是任意給定的正整數）的所有不可約數（素數），只要把1及不超過N的所有正合數都刪去。由於不超過N的正合數 a 必有一個不可約除數 p≤a的開方≤N的開方，因而，只要先求出不超過N的開方的全部不可約數（素數）P1，P2，…，Ps，然後依次把不超過N的正整數中的除了P1，P2，…，Ps以外的P1的倍數，P2的倍數，…，Ps的倍數全部刪去，就刪去了不超過N的全部正合數，剩下的就是不超過N的全部不可約數（素數）。