一个新的素数筛选法

在初等教论中,历来只知道艾氏(Eratos-thenes)素数筛法。本文给出一种新的素数筛选程序,它依赖于如下命题。定理 (张文亮)2n 1为(奇)素数的充分必要条件是n≠(2k 1)m k(n,m,k∈N)。证明如果2n 1为合数,则必为二奇数之积,即有m,k∈N,使得2n 1=(2m 1)·(2k 1),则 n=(2k 1)m k反之,如果对某m,k∈N,使得n=(2k 1)m k,则 2n 1=2(2k 1)m k] 1 =(2m 1)(2n 1)为合数,因此2n 1为(奇)素数的充要条件是:对任何m,k∈N,自然数n≠(2k 1)m k 定理表明,当n跑遍N={s|s≠(2k 1)·m k,s、m、k∈N}时,2n 1遍历奇素数集,