梁增勇

摘 要：

在研究质数的问题中常常运用到筛法计算质数的个数。本文介绍用更苛刻的筛除法求出质数对的可靠下限，同时用函数等数学分析的方法进行分析，即可解决这类性质的关键问题。

关键词：集合；函数；筛法；整数对；数学分析

一、本文使用的数学符号的定义：

全体非负整数的集合通常简称非负整数集（或自然数集），记作N[1]。本文中

A表示[1，n]区间正整数的集合，即A ={1，2，3，…，n}， 集合A的元素个数记为card （A）；

A＼-p为含有p素因子倍数的子集， 即A＼-p ={1p，2p，3p， 4p， 5p，……}， A＼-＼{2，3＼}={2，3，4，6，8，9}，（n=10） ；

B＼-p 为集合A不含p素因子合数子集（除了2），例如B＼-2是奇数的子集， B＼-＼{2，3＼}={1，3，5，7}，（n=10）；

P表示素数的集合，p或p＼-m 表示素数，即P={2，3，5，7，11，13，……， p， ……，} 或 P = {p＼-1 ， p＼-2 ， p＼-3 ，…， p＼-m ，…}，

ф（n）为欧拉函数，ф′（n）、h（n）为非合数个数的下限函数。d（n）为质数对个数的下限函数。

容斥原理是在组合数学中应用颇为广泛的一个工具，它常使用到容斥公式[2]。例如：

例1 设A是一个由整数组成的有限集合，d＼-1， d＼-2， …， d＼-m 是给定的正整数，再设A＼-d 表A中被正整数d整除的元素组成的子集，那么，A中不能被任一dj（1≤j≤m）整除的元素的个数等于

|A | -Σ1≤i≤m|Ad＼-i| + Σ1≤i≤j≤m|Ad＼-j∩ Ad＼-j |-… + （-1）＼+＼{m-1＼} | Ad＼-1∩ Ad＼-2∩…∩Ad＼-m|

由于取整運算十分是复杂， 仅可以在小范围内计算。对于更大范围的数据运算是无能为力的。下面我们介绍运用筛法、函数和数学分析解决这类性质的问题的几个对策和方法。

1、质数个数的下限函数

引理1[2]. 若p为任一质数，A＼-p 为n个连续自然数中含质数p的所有倍数的集合，则

card（A＼-p）≤np]= [kn+rp]=k ≤np = k+rp，因为 （rp ≥0） ， 所以 card（A＼-p）≤np 。

定理1. 若p为任一质数，B＼-p 为n个连续自然数筛除去质数p的所有合数的集合，则

Card（B＼-p）≥n（1-1p ）。

证 由引理1得，card（A＼-p） ≤np ，则card（B＼-p）=n-card（A＼-p）≥n-np = n（1-1p

）。

引理2 （Euler函数）[3] 若 n含任意质数p＼-i、p＼-j、……p＼-k 之因子，则 ф（n）= n （1-np＼-i ） （1-np＼-j）…（1-np＼-k） （1）

定理2. 若2，3，…，p＼-i为质数，p＼-i≤（2）

证 由引理2 可知， 函数φ（n） 是当n为2×3×5×……×p＼-k 时可计算得之准确值，当n与上述整数有互素的情况，因函数ф（n）转为ф′（n） ，由定理1可知每个因子（1-n22P＼-1 ） （ 1-2P＼-22P＼-i ）（3）

证 集合H的2n自然数可排成上、下两行组成n个相同性质的对偶数对，并筛除所有含合数的对偶数对。根据定理2，仅筛除上行含合数的对偶数对，余下个数为 card（B＼-＼{2，3，…，P＼-＼{i+1＼}＼} ）≥ф′（n）= n （1-13）…（1-1P＼-i）

再考虑对带奇合数对偶数重复筛除一次，即将括弧中1/p＼-i改为2/p＼-i，得到

card（B＼-＼{2，3，…，P＼-＼{i+1＼}＼}）≥d（n）= n（1-23）…（1-2P＼-i）

此即所谓重复筛除法，函数d（n）必然小于或等于非合性质元素对偶数对个数的实际值card（D）， 即

card（D） ≥d（n） = n2（ 1-2P＼-2） （ 1-2P＼-2 ）…（ 1-2P＼-i）

定理4 令N′为N之子集 ，card（N′）=2n ，2n≤p＼-m＼+2+1， 那么当

n2Πmi=2（1-2P＼-i）≥4（4）

成立，必定有一对或一对以上的同性质（例如相关质数）对偶数对存在。

证 已知N′的元素排列成n组同性质对偶数。由定理3可知，集合D已经不含任何的合数，d（n）为集合D元素个数的下限函数。 那么，当d（n） ≥ 4 （ 取保守一点） ），可组成至少两对对偶数（可能有一对含数1）这样，至少 有一对或一对以上对偶数对全是同性质整数存在。

定理5 令N′为N之子集 ，card（N′）=2n ，2n≤p＼-m＼+2+1， 则

（5）

证 对m使用数学归纳法[2]：1）当 m=6， n=170，d（n′）= [参考文献]

[1] 同济大学应用数学系主编 . 高等数学.[M]高等教育出版社，1978 ：1-23.

[2]潘承洞，潘承彪. 初等数论. [M]北京大学出版社， 2003：71-76.

[3]G.H.Hardy，E.M.Wright，An Introduction to the Theory of Numbers.[M].人民邮电出版社， 2007：52-53.

（作者单位：广西妇幼保健院，广西 南宁 530000）endprint