3137 414347 5359 6167 717379 8389 9197 从例4我们可以看出100以内的素数分布情况,进一步可以 由上述例题求出n=10000以内的素数,这种求素数的方法 称为爱拉托斯散( Eratosthenes)筛法。随着n的增加,按照 上述方法判断出n是否为素数的时间复杂度为O(n2) 由定理1可以看出每个整数都有一个素因数,下面我们要证 明每个整数一定可以表示成素数的乘积。 定理2任一整数n>1都可以表示成素数的乘积,即 n=PP2…p,P1≤P2s…Sp (1) 其中p是素数 定理3素数有无穷多个 定理4形如4k-1素数有无穷多个。 上述两个定理都说明了一件事情:素数有无穷多个。若以 丌(x)表示不超过实数x的素数个数,记p为第n个素数,我 们很容易得到丌(x)的一个很弱的下界估计和p的一个很弱 的上界估计。31 37 41 43 47 53 59 61 67 71 73 79 83 89 91 97 从例 4 我们可以看出 100 以内的素数分布情况，进一步可以 由上述例题求出 n =10000 以内的素数，这种求素数的方法 称为爱拉托斯散（Eratosthenes）筛法。随着 n 的增加，按照 上述方法判断出 n 是否为素数的时间复杂度为 ( ) 2 1 O n 。 由定理 1 可以看出每个整数都有一个素因数，下面我们要证 明每个整数一定可以表示成素数的乘积。 定理 2 任一整数 n 1 都可以表示成素数的乘积，即 n = p1 p2 pr， p1  p2  pr （1） 其中 i p 是素数。 定理 3 素数有无穷多个。 定理 4 形如 4k −1 素数有无穷多个。 上述两个定理都说明了一件事情：素数有无穷多个。若以 (x) 表示不超过实数 x 的素数个数，记 n p 为第 n 个素数，我 们很容易得到 (x) 的一个很弱的下界估计和 n p 的一个很弱 的上界估计