爱拉托塞斯筛法(Eratoshenes筛法)是一种寻找素数的方法,又称平凡除法或厄拉托塞斯(Eratoshenes)筛法。 其是应用定理“设n是正整数,如果对虽有的素数p≤√n,都有p不能整除n,则n一定是素数.”得到的一个寻找素数的确定性方法。下面给出具体描述: 对任意给定的正整数N,要求出所有不超过N的素数。列出N个整数,从中删除不大于√N的所有素数P1,P2,P3,……,Pk的倍数(除素数P1,P2,P3,……,Pk外)。具体的是依次删除, P1的倍数:2·P1,3·P1,4·P1,……,[N/P1]·P1; P2的倍数:2·P2,3·P2...