《2016.3寻找小于y素数的个数》.pdfVIP

寻找小于y质数的个数 寻找小于y质数的个数 寻寻找找小小于于yy质质数数的的个个数数 作者：建中2010-3-14 作者：建中2010-3-14 作作者者：：建建中-33--1144 所谓质数就是指除了可以被1和自身整除之外，不能被其他整数（如2、3、4 等数）整除的整数。简单点说就是不可再分的数。例如9个可以分成3等分，而7 个就不好分：分给两个人，一人三个剩一个；分给三个人，一人两个也是剩一个。 分给四、五、六个人都遇到同样的问题，不能恰好分完。当然七个人分，一人一个， 这是和要分的数目相同的情况。要是分给多于七个人，那么一个人连一个都分不到。 这些都是基本事实，下文就不多说了。 下面我将按一般规律去寻找小于y的质数有多少个。 数分奇偶，形如2m的任何偶数（除了2×1=2之外）都不是质数。能表为 (2m+1)(2n+1)的奇数（其中m≥1,n≥1）都不是质数。因为这两种情况都可再分， 都不符合质数的定义。 设 或 ，要求小于y的质数有多少个。 设 或 ，要求小于y的质数有多少个。 设设y= 2k+1或或y= 2(k+1)，，要要求求小小于于yy的的质质数数有有多多少少个个。。 由已知可知质数在 k 个奇数（从 3 到 y）中挑选，而且需要减去形如 ( )( )的奇数的个数。这些奇数有多少个呢？ 2m+1 2n+1 (2m+1)(2n+1)=4mn+2(m+n)+1=2(2mn+m+n)+1 当m=1，n=1（简记为(1,1)），得到 (2mn+m+n) = 2×1×1+1+1= 4 一个坐标就对应一个(2mn+m+n)值。所以我们只有算出小于等于k有多少个 坐标，就粗略知道有多少个不是质数的奇数。用k减去就得到小于y的质数的个数 了。这是初步设想。 k−1 k− 2 当m=1时，3n+1≤k得n≤ ；当m= 2时，5n+ 2≤ k得n≤ 等等。不 3 5 过这时我们发现坐标的个数不是所求出的n，因为(1,2) = (2,1)，(1,3)= (3,1)。所以为 k−1 k−2 了不重复计算，当m =1时n≤ − 0；当m = 2时n≤ −1。 3 5 ⎡ k−n ⎤ 写出 一 般 的 公 式 就 是 ： 质 数 个 数 = k− − (n−1) −⋯ 当然 ⎢2n+1 ⎥ ⎣ ⎦ ⎡ k−n ⎤ k−n −(n−1) ≥ 0即 。需要解释一下：[ ]是指求x的整数部分。 ⎢2n+1 ⎥ 2n+1−(n−1)≥1 x ⎣ ⎦ 即 2 求出 2k+1−1。 2n +2n−k≤0