Python一亿以内的素数个数_素数诸多问题的反证法（李扩继）

素数诸多问题反证法指的是：素数的存在性问题的反证法，孪生素数的存在性问题的反证法和哥德巴赫猜想存在性问题的反证法。

①素数是无限性的

素数即质数，仅能被自身和1所整除的正整数。1很特殊，不能做素数，但它是奇数。与素数相矛盾的数是合数。合数至少能分解成两个素数之积。由于把1不作为素数，就排除了一个素数P，1×P=合数的情况。偶数和奇数能以被2所整除和不能被2所整除来区分。把1排除在素数之外后，素数和合数就可以由它的素因子数个数为1个素因子数和至少两个素因子数个数来区分。

正整数=正奇数+正偶数=1+正素数+正合数。在我们叙述问题时，提到奇数，偶数，素数和合数时，都默认它们是正整数。

由于素数不能被其他素数所整除，因此，我们无法确定第n个正整数是不是素数，特别当n非常大时。对于n不太大时，用不大于√n的素数试除n，当所有素数都不能整除n时，即n为素数。因为，n若为合数，它的最小素因子数不会超过√n，所以，对于n以内的正整数，我们可以用不大于√n的所有素数能把它们的所有合数排除掉，常习惯称为筛掉。也就是说，我们只能是在排除合数的过程中得到素数。

素数是无限的证明，最经典的是欧几里得的反证明方法，他的方法是这样：假设素数是有限的，仅有2，3，…，P这些素数，那么，2×3×…×P+1这个数就不能被2，3，…，P所整除，所以，它要么是一个新素数或者是一个合数，而这个合数的素因子数也是一个新素数。这样就导置出了矛盾。由此，判断素数是无限的。

我给出的素数是无限的反证法是这样，假设素数是有限的，仅有素数为2，3，…，q，P。制造数域A={1，2，…，n}（n=P×P），那么，用2，3，…，q，P就能把集合A中的所有合数筛除掉，由假设，筛除含2，3，…，P的因子数后，集合A中仅留下了1。

由正整数的属性，连续的k（素数）个整数中，仅有一个数能被K所整除。如{1，2，3，4，5}或{4，5，6，7，8}中，仅有一个数被5所整除。集合A中含K因子的数为[n/K]个（[a]表正数a的整数部分），有（n-[n/k]）个数与k互质，至少有（n-n/k）与k互质。由欧拉函数筛法知，每筛除一个筛码素数因子后，留下的数依然成等差数列。因此由乘法原理知，集合A中，与2×3×…×q互质的数的比例是（1-1/2）（1-1/3）…（1-1/q），至少有[n（1-1/2）（1-1/3）…（1-1/q）]个数与2×3×…×q互质。由假设，这[n（1-1/2）（1-1/3）…（1-1/q）]（极小值大于P）个数仅是1和P以及P的合数（至少有P-2个），除P×P外，其余的（P-3）个P的合数都大于P×P。显然，这与集合A的数不大于P×P相矛盾。所以，集合A中至少有（P-3）个新的素数存在。所以，素数是无限的。

素数的存在性，孪生素数问题的存在性和"1+1"问题的存在性，它们三个是同一类问题。用素数无限性问题的反证法，也可以类似的证明其他两个问题。

结论：若用A（n）表集合A中自然数与2×3×…×P互质的自然数个数，那么，A（n）≥[n（1-1/2）（1-1/3）…（1-1/P]≥[√n]。

②孪生素数是无限的

孪生素数，如（3，5），（5，7），（11，13）等，若P和（P+2）都是素数，称（P，P+2）为孪生素数对。孪生素数是否是无限的？一直困惑着全世界的数学界。其实，这个问题在初等数学层面上可以完全解决。

和素数是无限的问题的证明方法一样，孪生素数是无限的问题也可以用反证法来证明。

假设，孪生素数是有限的，最大的孪生素数是（q，P），其中，P=q+2。

建立孪生素数的存在数域，令B={（-1，1），（0，2），（1，3），…，（n-2，n）}（P×P=n）；扩充集合B：{（-1，1），（0，2），（1，3），…，（n-2，n），…，（m-2，m）}（m=2×3×…×P）。用连续的素数2，3，…，q，P（P×P=n）就可以把集合B中含它们因子的元素筛尽，仅留下了（-1，1）。由于集合B中元素的一个重要属性：任意相邻的2个数元素中，仅有一个元素含2的因子数；任意连续的k（素数，大于2）个元素中，仅有二个元素含k的因子数。如果K能整除n，则集合B有n（1-2/k）个元素与K互质；如果K不整除n，n=aK+b，b是余数（a≠0，K>b>0），由于第一个元素到第K个元素是（-1，1），（0，2），…，（k-2，K），含k因子数的是第二个元素和第K个元素。余下的b个元素中，在第二个元素中含K因子数，其他元素都不含k因子数。所以，在余下的b个元素中，至少有（b-1）个元素与k互质，算式表示为[n（1-2/K）]=[（aK+b）（K-2）/k]=a（k-2）+[b（k-2）/K]，有（b-1）≥[b（k-2）/K]，即，在集合B中，至少有[n（1-2/K）]个元素与K互质。由欧拉函数筛法知，筛除了含2因子的元素后，扩充集合B中留下了m（1-1/2）个元素与2互质，筛除含3因子的元素后，留下了m（1-1/2）（1-2/3）个元素与2×3互质，…，筛除含q因子的元素后，留下了m（1-1/2）（1-2/3）…（1-2/q）个元素与2×3×…×q互质。因此由乘法原理知，集合B中或扩充集合B中与2×3×…×q互质的元素个数的比例是（1一1/2）（1一2/3）…（1一2/q），所以，集合B中，至少有[n（1一1/2）（1一2/3）…（1一2/q）]（最小值大于P/2，P≥3）个元素与2×3×…×q互质。由假设，筛除了含2，3，…，q的因子数的元素后，集合B中留下了（-1，1），和可能留下了（P-2，P）与（P，P+2）外，其他都是含P的合数的元素。这样，除了（-1，1）和（P×P-2，P×P）外，其他元素中至少有一个数大于P×P（P/2-3≥1）。但这与集合B中元素除（P×P-2，P×P）外，其他元素中的数都小于P×P相矛盾。所以，假设不真，孪生素数是无限的。

结论：若用B（n）表集合B中元素与2×3×…×P互质的元素个数，那么，B（n）≥[n（1一1/2）（1一2/3）…（1一2/q）（1一2/P]≥[√n/2]。

③哥德巴赫猜想

大于4的偶数表两个素数之和的问题，简称为“1+1"问题，人们称哥德巴赫猜想。如4=2+2为唯一的偶素数之和，6=3+3，8=3+5等。是不是所有的偶数都存在可用两个素数之和来表示？这是近三百年之问，人们做了许多努力，都没有完全解决。其实，它和素数存在性，孪生素数的存在性问题一样，在初等数学的层面上，完全可以证明。

把一个偶数2n分拆成两个整数之和，用数域C来表示，C={（1，2n-1），（2，2n-2），…，（n，n）}（Pt×Pt≤2n）以及扩充集合C：{（1，2n-1），（2，2n-2），…，（n，n），…，（m，2n-m）}。用连续的素数2，3，…，Pt（Pt×Pt≤2n）筛除集合C中含它们因子的元素，留下来的元素就是“1+1"元素。

假设，存在偶数2n（n>2），表两素数之和的个数为0，即对于集合C中的元素与2×3×…×Pt互质的元素个数为0（注：素数k与元素互质，指K与元素中的两个数都互质）。

由扩充集合C中的元素属性，相邻的两个元素仅有一个元素含2的因子数；任意连续的k（素数）个元素中，当K整除2n时，仅有一个元素含K的因子数，当k不整除2n时，仅有二个元素含k的因子数。因此，对于集合C，如果K（素数）能整除n，则有n（1-1/2）个元素与K互质；如果K不整除n，n=aK+b，b是余数（a≠0，K>b>0），由于第一个元素是（1，2n-1），第K个元素含K因子数。所以，余下的b个元素中，至少有（b-1）个元素与k互质，算式表示为，[n（1-2/K）]=[（aK+b）（K-2）/k]=a（k-2）+[b（k-2）/K]，有（b-1）≥[b（k-2）/K]，即，至少有[n（1-2/K）]（[a]表正数a的整数部分）个元素与K互质（Pt整除2n时，ri=1，Pt不整除2n时，ri=2；其他素数亦然）。由欧拉函数筛法，筛除含2因子的元素后，扩充集合C中留下了m（1-1/2）个元素与2互质，筛除了含3因子的元素后留下了m（1-1/2）（1-r2/3）个元素与2×3互质，…，筛除了含P因子的元素后留下了m（1-1/2）（1-r2/3）…（1-rt/Pt）个元素与2×3×…×Pt互质，由乘法原理，筛除含2，3，…，P的因子数后，集中C或扩充集合C中与m互质的元素个数比例是（1-1/2）（1-r2/3）（1-r3/5）…（1-ri/p），所以，至少有[n（1-1/2）（1-r2/3）（1-r3/5）…（1-ri/p）]≥[n（1-1/2）（1-2/3）（1-2/5）…（1-2/p）]≥[√2n/4]（n≥8）个元素与2×3×…×P互质。所以，假设不真，哥德巴赫猜想成立。

结论：若用C（2n）表示集合C中，与2×3×…×P互质的元素个数（P×P≤2n），那么，C（2n）≥[n（1一1/2）（1一r2/3）…（1一ri/P）]≥[n（1一1/2）（1一2/3）…（1一2/P）]≥[√2n/4]。

参考文献

1.李科技《哥德巴赫猜想的证明》（A），2008。

2.李扩继《再证哥德巴赫猜想》（J），2017。

3李扩继《容斥原理的应用》（J），2020。