自然数网络和素数定理

素数分布论

素数分布论 作者姓名：弯国强 作者单位：漯河市舞阳县莲花镇仁和小学 E-mail ：632158@https://www.wendangku.net/doc/9711499502.html, 摘 要：素数分布主要研究什么呢？我认为主要应从三个方面进行研究：一、素数的个数公式；二、素数的生成公式；三、素数分布的性质。精确的素数个数公式，是研究素数分布的基础，离开了素数个数公式的研究，素数分布的研究就是无源之水，素数个数公式的研究一直是素数分布中的一个重要问题，因此，我们首先要研究素数的个数公式；其次找到素数的生成公式一直是人们梦寐以求的理想；最后就是对素数的各种性质进行研究，这样才能对素数的分布有的一个全面的理解。本文围绕素数的分布，利用分析的观点，证明了真正的素数定理： ()1 1ln ln 2( ) ln n n n o n ππγ= +-+-- 摈弃了原来粗糙的素数定理的近似公式 ()ln x x x π≈ 深刻揭示了欧拉函数与素数个数之间的关系以及欧拉函数分析化的一个重要结论 ()()1n n m ?π=-+，()1ln ln 2( ) ln n n n o n ?γ= +-- 找到人们梦寐以求的能够生成全体素数的素数公式 1212' ' ' '2 111 ,(,) (1),1(m od ),0(m od ),1,(m od ),{(m od ),01) ,2[} ,i i k i k i i i i i i i i i j k i i i k k i M M p p p M p p p p M i k M M p M M p j k i j N n n a p a p a M M M N p i k p π++=== ≤≤≡≡≤≤≡<<≤ =≡ =≠∈∑ 设为连续的质数那么存在整数使得 素数公式为 关键词：素数、合数、筛法、素数分布、素数定理、素数公式 中图分类号：O156.1 素数在纯数学中是一个使数学家迷恋的字眼，它是那么简单，又是那么神秘。说它简单是因为它是整数的基石，既便是上过小学的学生都知道什么是素数；但是它又那么神秘，从古至今，多少数学家都想弄明白它的规律，却始终无法弄明白它的分布规律是什么。素数在自然数中占有极其重要的地位，但是它的变化非常不规则。素数分布就像一首神奇的乐章，

最精确素数定理的发现及证明

最精确素数定理的发现及证明 山东章丘一职专马国梁 大家知道：素数的序列曲线是一条单调增长的不规则连线。而关于究竟有没有一条能够贯穿始终的中轴线及方程的问题，多少年来人们一直在进行苦苦的探索。虽然曾有人根据统计规律进行归纳推测，也有人利用其它方程的曲线向其靠近，但皆由于证据不足而难以令人信服。所以至今竟使不少人怀疑中轴线的存在，更谈不上写出它的方程。 笔者经过长时间的分析研究后认为：之所以至此，是因为在研究方向上发生了偏差。素数本身是没有规律的，它的统计规律只是一种表面现象，而不是其内在本质。所以要想弄清它的根本原因，我们必须从素数的产生机制上着手，才能有所突破。幸运的是：笔者沿着这个正确的方向，终于取得了成功。虽然研究过程十分艰难，好多次试探都归于失败。也曾几度走投无路，意欲放弃，但不想又峰回路转，绝路逢生。整个过程一波三折，思想左右摇摆。因为笔者也不知这条中轴线究竟是否存在。如果它根本就不存在，那笔者的研究岂不成了捕风捉影？毫无成功的可能！但幸好实际情况不是这样。下面笔者就将自己的研究结果做如下介绍。 我们知道：“埃氏筛法”是寻找素数最基本最有效的方法。其实这个方法不光适用整个自然数轴，它也适用于局部范围。所以在任一素数Pi之后的一段长度里（P i+1 - P i），当它被前面的所有素数筛漏的只剩下1个单位时，那么就要产生新的素数了。 当然这种筛选我们没有必要用上P i之前所有的素数，而是只用sqrt(P i) 前面的所有素数就可以了。其中最大的素数为P r P r≈sqrt(P i) 这样当[P i+1 - P i ][1/2] [2/3] [4/5] ……[(P r– 1)/P r ] = 1 时 将会有P i+1 = P i + [2/1] [3/2] [5/4] ……[P r /( P r - 1) ] 其中从2开始到P r的筛剩率连乘积的倒数就是新素数的理论间距。其大小为 ΔP r = [2/1] [3/2] [5/4] ……[P r /( P r - 1) ] = ΔP r -1 [P r /(P r– 1) ] 将素数间距改写成连续的方程y r = y r -1[x r /(x r–1)] 那么其平均导数是dy/dx = (y r /y r -1) -1 = 1/(x r–1)] = 1/(x –1) 从而得dy = dx/(x –1) 将两边积分得y = ln(x-1) + C 当积分区间是从2开始到x的定积分时，积分常数C 将被消去。 并且当x很大时，x – 1 项中的1可以略去，因而得 y = ln(x) y r = ln(x r) 可是实际验算证明：用这个公式计算的只是从3/2开始一直到P r /( P r - 1) 连乘积，所以若算ΔP r必须对其加倍，即 ΔP r = 2y r = 2 ln(x r) ≈ln(P i) 这个结果早期的理论推导也已经证明。现在大家也都知道：当x →∞时，素数的间距确实是趋于ln(P i) .由此得素数系列的递推式是 P i+1 = P i + ln(P i) 其中P1 = 2 我们可以利用这个式子将数据推算到无限远处，并把它的序列曲线画出来，这条曲线就是黎曼曲线。但是在P ～i 坐标系中我们发现：黎曼曲线总是在真实的素数曲线之下，且相距越来越远。所以同样的P 值，黎曼曲线将需要更大的序号。这就说明真实的素数平均增长幅度是大于ln(P i) 的，原先的素数定理是不准确的。 那么究竟应该怎样进行修正呢？笔者为此曾经绞尽脑汁，多方进行试探。在经过一系列失败后，笔者才终于醒悟到：原来我们忽略了一个重要乘项——尾倍率。 我们知道：P i是素数，所以它的平方根不可能是整数，更不可能是素数，所以进行筛选的最大素数P r肯定小于sqrt(P i) . 并且sqrt(P i) 的位置不是固定不变的，而是随机的。它可能略大于P r，也可能略小于P r+1 .虽然P r和P r+1的平均距离并不大，但是对于P i之后的素数增幅却影响很大。 P i+1的增幅是lnP i，而P i后面最大的增幅则是 ln[(P r+1)^2] = 2 ln(P r+1) = 2 ln[sqrt(P i) + ln(sqrt(P i))] ≈lnP i [1+1/sqrt(P i)] 前后的平均增幅是lnP i [1+0.5/sqrt(P i)]

华罗庚证明的哥德巴赫猜想与三素数定理、陈氏定理的比较

华罗庚证明的哥德巴赫猜想与三素数定理、陈氏定理的比 童信平 1742年6月7日，时任普鲁士派往俄罗斯的公使、数学业余爱好者哥德巴赫写 信给欧拉。同年的6月30日，欧拉回了信。这二封信确立了下面的二个哥德巴赫 猜想: 哥德巴赫猜想(A): “大于 4 的偶数可以写成二个奇素数相加。”又称为偶数哥 德巴赫猜想。简称“ 1+1” 哥德巴赫猜想(B): “大于7 的奇数可以写成三个奇素数相加。”又称为奇数哥 德巴赫猜想。 20 世纪20 年代，哈代和李特伍德二人进一步提出了这二个猜想的表法个数( 答案数量)的猜想:公式(1) 是偶数哥德巴赫猜想的表法个数(答案数量)的计算公式， 称为哈代-李特伍德猜想(A) 。公式(2) 是奇数哥德巴赫猜想的表法个数计算公式， 称为哈代-李特伍德猜想(B) 。参照素数定理的证明过程，需要通过公式(1a) 、(2a) 来证明公式(1) 、(2) ，条件是找到公式中前面的那些参变量和后面的0(1)并证 明，N??寸， 0(1)?0。 p-1N1 [1][2](1) r(n) ，2c(n) 【其中，c(n)(=c(N))= ? (1- ) ? 。】 222(p-1)p-2lnN 3?p?N p|N 3?p?N N[1][2](1a) r(n)(= r(N)) ，2c(N)(1+ 0(1)) 【要求找到前面的参变量和0(1) 并证明，N??寸，0(1)?0。】2221nN NNNl nInNNInIn N[3](1b) ①(N)= S(N)+ 0()=2 c(N) + 0() 1985 年，华罗庚指出，r(N)(= 15/25/222(lnN)(lnN)lnNlnN

数学实验素数的分布

数学实验作业（一） 素数的分布 一、 实验目的 观察素数在实轴上的分布，考查素数在实轴上的分布规律，寻找区间上素数个数的近似表达式. 二、 实验原理及步骤 1、用)(n π代表不超过n 的素数的个数，),(n m π表示区间],[n m 内素数的 个数.试计算),100(π),1000(π),1000(π),10000 (π),100000(π以及)200,100(π，)1100,1000(π,)10100,10000(π,)100100,100000(π.从计算结果看，随着整数范围的扩大，素数是越来越稀疏，还是越来越密？考虑一些更长的区间，再尝试以上同样的实验. 2、将素数从小到大顺序排列 ,3,221==p p ，用n n n p p d -=+1表示相邻素数之间的间隔.计算)10000,1000(,,,321=N d d d d N ，然后将点),(n n d p 标在坐标系中，试从中找出素数间隔的规律.比如素数的间隔值有哪些？它们各重复多少次，哪些间隔值重复的次数多，最大间隔是多少？随着N 增大，最大间隔值是否也随之增大？ 3、根据上述实验，对素数的分布做一个猜测，比如间隔为2的素数是否有无穷多个？更一般的，间隔为某个素数是否有无穷多个？是否存在相邻的素数，其间隔值可以无穷大？证明这些猜测. 4、在二维平面上标出点列))(,(n n π，N n ,,2,1 =（取不同的N ，如1000，10000等）.也可以用折线将点连接起来.观察)(n π趋于无穷的趋势，并且将它与 x y x y ==,比较.可以得出什么结论？类似的观察点列)/)(,(n n n π，)/)(,(n n n π及))))ln(//()(,(,(n n n n n ππ.猜测)(n π趋于无穷时候的极限. 5、令? ∑ ∞ ++==n k k n k k n R dx x n Li 2 1!)(ln ) 1(11)(,ln 1)(ζ，其中：

数论-第六章

5 1 0011 0010 1010 1101 0001 0100 1011 第六章素数计数 张志强智能信息处理研究中心 https://www.wendangku.net/doc/9711499502.html, 51 0011 0010 1010 1101 0001 0100 1011智能信息处理研究中心2 素数 ?素数是数论的基本构件 –前面的算术基本定理告诉我们，每个数都可唯一表示成一个素数幂次的乘积形式–化学中的基本元素 –核物理中的三种基本粒子，质子、中子和电子–软件行业中的构件 –……

510011 0010 1010 1101 0001 0100 1011智能信息处理研究中心3 素数 ?定理1(无穷多素数定理)：存在无穷多的 素数 ?证明(欧几里得)： –基本思想，假设有限，然后利用有限的素数构造出一个新的素数 –假设现有素数表为p 1,p 2,…,p r ，我们得到如下的数A=p 1*p 2*p 3*…*p r +1 –如果A 本身是素数，则证明完成，因为A 太大不在最初的表中。 51 0011 0010 1010 1101 0001 0100 1011智能信息处理研究中心4 素数 –如果A 不是素数，则其肯定会被某个素数整除，设q 是某个整除A 的素数，且设其为最小的那个，可知q 不在最初的表中（为什么？），所以它是期望的新素数。重复这个过程可创建素数表，这表明必有无穷过个素数。 ?尝试自己创建素数表 –最初素数表为{2} –第一次得{2,3}–第二次得{2,3,7} –第三次得{2,3,7,43} –……

51 0011 0010 1010 1101 0001 0100 1011智能信息处理研究中心5 素数 ?2是仅有的偶素数！ ?有时需要对素数进行分类，如(除2之外)–哪些素数模4余1？ –哪些素数模4余3？ 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179,… p ≡3(mod 4)5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, 137, 149, 157, 173, 181, 193, 197,… p ≡1(mod 4)510011 0010 1010 1101 0001 0100 1011智能信息处理研究中心6 素数 ?定理2：存在无穷多个模4余3的素数?证明： –采用与定理1同样的思想 –第1步，假设已经得到有限个的模4余3的素数表，{3, p 1,p 2,…,p r } –第2步，构造数A=4*p 1*p 2*p 3*…*p r +3 –第3步，将A 分解为素数乘积A=q 1*q 2*q 3*…*q s –第4步，证明q 1,q 2,q 3,…,q s 中必有一个q i 是模4余3的–第5步，证明这个q i 不在最初的表中

费马小定理 素数判定 蒙哥马利算法

费马小定理素数判定蒙哥马利算法(强烈推荐） 2009-11-07 12:42 费马小定理素数判定蒙哥马利算法 约定： x%y为x取模y，即x除以y所得的余数，当x

一些素数个数计算

一些素数个数计算 根据自然数数列因子分布规律和不遵从自然数数列的数列因子分布规律，用这两种方法建立计算公式求算素数个数. 标签：数列素数个数计算项差分布规律猜想 一、欧几里得素数 概念：都是整数，其形式为En=Pn+1，其中Pn是Pn的质数阶乘。 前几个欧几里得数3 7 31 211 2311 30031 510511 …… 因为是En=Pn+1，数列中的项差分布与自然数数列项差分布不同，所以，就不能用求自然数数列的奇质数方法计算。根据欧几里得数的阶乘性质和素数个数分布与计算原理，每一个欧几里得数是否奇质数，只能单独计算。 根据欧几里得数的性质，第1、2、3项欧几里得数不可能有因子，只能是奇质数；第4项211因子可能是11和13，不可能是2、3、5、7，以及≥17的奇质数，所以第4项是奇质数的可能性为1×10/11×12/13≈0.839，以后以此类推。欧几里得素数总个数计算公式F=1（第1项）+1（第2项）+1（第3项）+1×10/11×12/13（第4项）+1×12/13×16/17×18/19×22/23×28/29×30/31×36/37×40/41×42/43×46/47（第5项）+…… 随着欧几里得数的不断增大，F也不断缓慢增大，所以，欧几里得素数有无限个。 以上的单个计算方法，适合于随机抽取（项差不遵从自然数数列项差分布规律）的一组数列和自然数数列的奇质数个数计算。项数越多，计算值越准确。 二、费马素数 概念：形式为2n+1（n=2m，m取值为0、1、2、3……则n为1、2、4、8……）前几个费马数是3、5、17、257、65537、4294967297……求其中的素数个数。 从上面可以看出，项差不符合自然数数列分布规律，费马数数列只是2k+1（k取值为0、1、2、3……）数列中的一部分，可以参照上面的欧几里得素数素数计算方法求解。 当k≠1、2、4、8、16……2n数时，叫做非费马数。非费马数都可以进行因式分解，所以，非费马数都是合数，因子是绝大多数奇质数。以上可以得出结论，费马数是非费马数的因子，而非费马数中除费马数因子之外的因子不可能是费马数的因子。又因n=1、2、4、8、16……所以，费马数自身因子不循环分布，并

求素数的算法及其复杂度分析

求素数的算法及其复杂度分析2008-04-05 17:46关于搜寻一定范围内素数的算法及其复杂度分析 ——曾晓奇 关于素数的算法是信息学竞赛和程序设计竞赛中常考的数论知识，在这里我跟大家讲一下寻找一定范围内素数的几个算法。看了以后相信 对大家一定有帮助。 正如大家都知道的那样，一个数 n 如果是合数，那么它的所有的因子不超过sqrt(n)--n的开方,那么我们可以用这个性质用最直观的方法 来求出小于等于n的所有的素数。 num = 0; for(i=2; i<=n; i++) { for(j=2; j<=sqrt(i); j++) if( j%i==0 ) break; if( j>sqrt(i) ) prime[num++] = i; //这个prime[]是int型，跟下面讲的不同。 } 这就是最一般的求解n以内素数的算法。复杂度是o(n*sqrt(n))，如果n 很小的话，这种算法（其实这是不是算法我都怀疑，没有水平。当然没 接触过程序竞赛之前我也只会这一种求n以内素数的方法。-_-~）不会耗时很多. 但是当n很大的时候，比如n=10000000时，n*sqrt(n)>30000000000,数量级相当大。在一般的机子它不是一秒钟跑不出结果，它是好几分钟都跑不 出结果，这可不是我瞎掰的，想锻炼耐心的同学不妨试一试~。。。。 在程序设计竞赛中就必须要设计出一种更好的算法要求能在几秒钟甚至一秒钟之内找出n以内的所有素数。于是就有了素数筛法。 （我表达得不清楚的话不要骂我，见到我的时候扁我一顿我不说一句话。。。） 素数筛法是这样的： 1.开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false. 2.然后： for( i=3; i<=sqrt(n); i+=2 ) { if(prime[i]) for( j=i+i; j<=n; j+=i ) prime[j]=false; } 3.最后输出bool数组中的值为true的单元的下标，就是所求的n以内的素数了。 原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质 数的倍数筛掉。 一个简单的筛素数的过程：n=30。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

论给定区间素数的分布规律公式

论给定区间素数的分布规律公式 田永胜 （内蒙古自治区吉兰泰750333） 摘要：通过对自然数按照一定方向旋转排列，找到了自然数的等势区间并集，并对每个区间的素数分布情况进行研究，给出了在给定区间内素数的分布定理、公式及推论。 关键词自然数；螺旋排列；给定区间；素数分布；规律； 引言 自然数沿数轴方向排列时，素数的分布没有规律可循；当把自然数按一定的方向旋转排列时，素数的分布就变得有规律。下面揭示它的分布规律。 1 自然数的排列规律 首先，按逆时针方向把自然数进行排列，如下图： 自然数螺旋排列图 从上图可以看出，自然数集合N+也可以由一连串连续区间的并集组成，[1]∪（1，9]∪（9，25]∪（25，49]∪（49，81]∪（81，121]∪（121，

169]∪……∪（（2x-3）2，（2x-1）2]…。并且，每个区间的最大数都是奇数（2x-1）的平方。 2 素数分布定理和公式 首先，来研究每一区间数字的素数分布情况： 第一区间只有自然数1，素数个数为0。 第二区间为（1，9］，有8个数字，其中素数有4个，所占比例为4/8=0.5。 第三区间为（10，25］，有16个数字，其中素数有5个，所占比例为 5/16=0.3125； 第四区间为（25，49］，有24个数字，其中素数有6个，所占比例为6/24=0. 25；以此类推。 其次，再来看每一个区间的素数分布与区间内的数有什么内在规律。1在中心，不是素数；在区间（1，9］有8个自然数，最大数是9，求9的自然对数的倒数，1/ln9≈0.455，与该区间实际素数所占比例接近；乘以总数8，值约等于3.64，取整数后为4，与该区间实际素数个数相同。在区间（10，25］有16个自然数，最大数是25，求25的自然对数的倒数，1/ln25≈0.311，与区间内实际素数所占比例0.3125很接近，乘以总数16，值约等于4.97，取整数后为5，与该区间实际素数个数相同。在区间（25，49］有24个自然数，最大数是49，求49的自然对数的倒数，1/ln49≈0.2569，与区间内实际素数所占比例0. 25很接近，乘以总数24，值约等于6.16，取整数后为6，与该区间实际素数个数相同。以此类推，如素数分布规律表所示。

质数分解

★引子 前天，俺在《俺的招聘经验[4]：通过笔试答题能看出啥？》一文，以"求质数"作为例子，介绍了一些考察应聘者的经验。由于本文没有政治敏感内容，顺便就转贴到俺在CSDN 的镜像博客。 昨天，某个CSDN网友在留言中写道： 老实说,这个程序并不好写,除非你背过这段代码 如果只在纸上让别人写程序,很多人都会出错 但是如果给一台电脑,大多数人都会把这个程序调试正确 出这个题目没啥意义 只能让别人觉得你出题水平低 首先，这位网友看帖可能不太仔细。俺在文中已经专门强调过了，评判笔试答题，"思路和想法"远远比"对错"更重要，而他/她依然纠结于对错；其次，这位网友居然觉得这道题目没啥意义，这让俺情何以堪啊？！看来，有相当一部分网友完全没有领略到此中之奥妙啊！ 算了，俺今天就豁出去了，给大伙儿抖一抖这道题目的包袱。当然，抖包袱的后果就是：从今天开始，就得把"求质数"这道题从俺公司的笔试题中去掉，然后换上另外一道全然不同的。这么好的一道题要拿掉，真是于心不忍啊 :-( ★题目 好，言归正传。下面俺就由浅入深，从各种角度来剖析这道题目的奥妙。 为了避免被人指责为"玩文字游戏"（有些同学自己审题不细，却抱怨出题的人玩文字游戏），在介绍各种境界之前，再明确一下题意。 前一个帖子已经介绍过，求质数可以有如下2种玩法。 ◇需求1 请实现一个函数，对于给定的整型参数 N，该函数能够把自然数中，小于 N 的质数，从小到大打印出来。 比如，当 N = 10，则打印出 2 3 5 7 ◇需求2 请实现一个函数，对于给定的整型参数 N，该函数能够从小到大，依次打印出自然数中最小的 N 个质数。

比如，当 N = 10，则打印出 2 3 5 7 11 13 17 19 23 29 ★试除法 首先要介绍的，当然非"试除法"莫属啦。考虑到有些读者是菜鸟，稍微解释一下。 "试除"，顾名思义，就是不断地尝试能否整除。比如要判断自然数 x 是否质数，就不断尝试小于 x 且大于1的自然数，只要有一个能整除，则 x 是合数；否则，x 是质数。 显然，试除法是最容易想到的思路。不客气地说，也是最平庸的思路。不过捏，这个最平庸的思路，居然也有好多种境界。大伙儿请看： ◇境界1 在试除法中，最最土的做法，就是： 假设要判断 x 是否为质数，就从 2 一直尝试到 x-1。这种做法，其效率应该是最差的。如果这道题目有10分，按照这种方式做出的代码，即便正确无误，俺也只给1分。 ◇境界2 稍微聪明一点点的程序猿，会想：x 如果有（除了自身以外的）质因数，那肯定会小于等于 x/2，所以捏，他们就从 2 一直尝试到 x/2 即可。 这一下子就少了一半的工作量哦，但依然是很笨的办法。打分的话，即便代码正确也只有2分 ◇境界3 再稍微聪明一点的程序猿，会想了：除了2以外，所有可能的质因数都是奇数。所以，他们就先尝试 2，然后再尝试从 3 开始一直到 x/2 的所有奇数。 这一下子，工作量又少了一半哦。但是，俺不得不说，依然很土。就算代码完全正确也只能得3分。 ◇境界4 比前3种程序猿更聪明的，就会发现：其实只要从 2 一直尝试到√x，就可以了。估计有些网友想不通了，为什么只要到√x 即可？ 简单解释一下：因数都是成对出现的。比如，100的因数有：1和100，2和50，4和25，5和20，10和10。看出来没有？成对的因数，其中一个必然小于等于100的开平方，另一个大于等于100的开平方。至于严密的数学证明，用小学数学知识就可以搞定，俺就不啰嗦了。◇境界5 那么，如果先尝试2，然后再针对 3 到√x 的所有奇数进行试除，是不是就足够优了

有趣的大素数分布统计

有趣的大素数分布统计 素数，飘忽不定、乱云飞渡。 素数，普遍认为的分布规律是没有规律。 素数，时而连续，时而相隔很远。有远亲、有近邻。 人们已经习惯了小区间的素数分布情况，并认可其为真理，比如以下几点： 1、统计10以内有4个素数，素数占40%，100以内有25个素数，素数占25%，1000以内有168个素数，素数占16.8%。这种观念和方法可以说是根深蒂固。当然“素数越来越稀少”这个结论更是牢不可破。 2、以10倍增长来考察素数分布规律。几乎所有关于素数个数统计的文章中都是按照10，100，1000，10000等10倍增长来统计相应自然数内的素数个数。 而在大区间情况又是怎样的呢？它和我们头脑中的素数观一致吗？还是列举一些实例吧，体会一下也许与上述小区间素数观念不一样的素数观。 先列出10000附近的素数来体会，虽然数字太小，但也许还是可以发现一些端倪的。 这里将相邻两个区间按照排列顺序简称为前区和后区。 首先展示自然数10000左右的素数分布情况。

以10000为中心，以100为区间大小。也就是说9900-10000为前区，10000-10100为后区。在前区素数个数为9个，后区为11个，前后区个数比值为0.82。两者结果相差18%。而若以1000为区间大小，前区为112个后区为106个，前后区个数比值为1.06。相差还是有些大的。如果非常认真的人一定会认为两区间所含素数个数相差很大，而一些马马虎虎的人就可能认为两者差不多吧。相同的统计结果在不同的人群中还是可能有些认知差别的。 那还是看一下大数字下的素数统计分布情况。 以下统计都是以100亿为中心，以100亿的1%为区间大小，也就是说个前后两个区间长度各为1亿。下面按素数、孪生素数、三胞胎素数、四胞胎素数分述如下： 一、素数的分布 前后区分别包含4343734和4341930个素数，前后区个数比值为1.0004，仅仅相差0.04%。与前文自然数10000时“相差16%”的统计结果中可以说是天壤之别了。前后区分别包含了1086253和1085898个个位为1的素数，前后区个数比值为1.0003；前后区分别包含了1086064和1084787个个位为3的素数，前后区个数比值为1.0012；前后区分别包含了1086118和1085574个个位为7的素数，前后区个数比值为1.0005；前后区分别包含了1085299和1085671个个位为9的素数，前后区个数比值为0.9997。

质数那些事(含答案)

专题01 质数那些事 阅读与思考 一个大于1的自然数如果只能被1和本身整除，就叫作质数(也叫素数)；如果能被1和本身以外的自然数整除，就叫作合数；自然数1既不是质数，也不是合数，叫作单位数．这样，我们可以按约数个数将正整数分为三类： 1?? ??? 单位正整数质数合数 关于质数、合数有下列重要性质： 1．质数有无穷多个，最小的质数是2，但不存在最大的质数，最小的合数是4． 2．1既不是质数，也不是合数；2是唯一的偶质数． 3．若质数p |ab ，则必有p |a 或p |b ． 4．算术基本定理：任意一个大于1的整数N 能唯一地分解成k 个质因数的乘积(不考虑质因数之间的顺序关系)： N= 12 12 k a a a k P P P ，其中12k P P P << <，i P 为质数，i a 为非负数(i =1，2，3，…，k )． 正整数N 的正约数的个数为(1＋1a )(1＋1a )...(1＋1a )，所有正约数的和为(1＋1P ＋ (11) P )(1＋2 P ＋…＋22a P )…(1＋k P ＋…＋k a k P )． 例题与求解 【例1】已知三个质数a ，b ，c 满足a ＋b ＋c ＋abc =99，那么a b b c c a -+-+-的值等于_________________． (江苏省竞赛试题) 解题思想：运用质数性质，结合奇偶性分析，推出a ，b ，c 的值．

【例2】若p为质数，3p＋5仍为质数，则5p＋7为( ) A．质数B．可为质数，也可为合数 C．合数D．既不是质数，也不是合数 (湖北省黄冈市竞赛试题) 解题思想：从简单情形入手，实验、归纳与猜想． 【例3】求这样的质数，当它加上10和14时，仍为质数． (上海市竞赛试题) 解题思想：由于质数的分布不规则，不妨从最小的质数开始进行实验，另外，需考虑这样的质数是否唯一，按剩余类加以深入讨论．

素数分布基本定理

素数分布基本定理 作者姓名：弯国强 作者地址：漯河市舞阳县莲花镇第二初级中学 E-mail ：632158@https://www.wendangku.net/doc/9711499502.html, 我们可以把自然数列按照某个自然数分段，并把这个分段记为T ，r T 表示第r 个分段。例如：按照自然数3分段，就是每隔3个数分一段。 1，2，3；4，5，6；7，8，9；………… 第1段为1，2，3记为1{1,2,3}T =，……第r 段记为{32,31,3}r T r r r =-- 按照自然数5分段，就是每隔5个数分一段。 1，2，3，4，5；6，7，8，9，10；11，12，13，14，15；………… 第1段为1，2，3，4，5记为1{1,2,3,4,5}T =，……第r 段记为 {54,53,52,51,5}r T r r r r r =---- 我们把第1分段中的全部质数叫基质数。例如1{1,2,3}T =中的基质数为2，3 1{1,2,3,4,5}T =中的基质数为2，3，5 定理：1 设T 是自然数的任一分段，在()2 1n n + 内，分段r T 中基质数倍数的个数不大 于分段1T 中基质数的倍数的个数。 证明： 设1{1,2,3,,}T n = ，12,,m p p p 是1T 中的基质数。 集合{1,2i A p i m == 质数的倍数,｝ ，1A T ?，那么由容斥定理我们可以得到，A 中元素的个数为()1 111m m m m m i i j i j k i i j i j k i i n n n n p p p p p p p -=<<<=?? ??????????-+++-?????????????????????? ∑∑∑∏ 集合{1,2i B p i m == 质数的倍数,｝，r B T ?，设B 中元素的个数为S B 中元素的个数最多为m S 当m n p ≠时，由于 12,,m p p p 是不超过n 的所有质数，所以n 至少能被12,,m p p p 之一整除，否则n 为质数，这与m p 是n 中最大的质数矛盾。当m n p =时，m p n 。故n 至

素数分布密度

素数分布密度 郭占祥 Ⅰ. 素数分布密度 1792年，高斯建议用1/log x表示大整数x附近素数分布平均密度，1850年切比雪夫证明C1·x/log x＜π(x)＜C2·x/log x,后来又有新的改进，966、1973年， 数论家CJR证明充分大偶数E=一个奇素数（P1）＋一个奇素数（P2）×一个奇素数（P3）。但是当x→∞时，由于误差项π(x)-log x→∞不能克服，所以数学家 们只能在充分大的奇数、偶数上用近似方法证明相关素数问题，不能在无限大奇数、偶数上彻底证明相关素数问题。充分大偶数超过10的50万次方，随着量子计算机的诞生人们将抛弃“素数定理式”的方法证明素数问题。数论家们将不再弃简就繁，而要走向埃腊脱士散尼筛法正轨。用素数倍数法（整除法）是能够证明素数相关命题的。 在非1自然数列2,3,4,…,n,n+1,…上，筛去不大于P n的有限素数2,3,5,…, P n 的倍数后，数列上剩余的最小数n01一定是第n+1个素数P n+1．无论第n个素数 P n有多大，都是如此，所以素数有无穷多。 在非1奇数列3,5,7,9,…,d,d+2,…上，设第n对儿孪生素数为(p f,p s)n,筛去含有奇素数3,5,7,11,…,23,…, p f,p s倍数的孪生数后，孪生数列上乘余的最小孪生数n21一定是第n+1个孪生素数(P f ,P f )n+1．无论第n对儿孪生素数(P f ,P f )n有多大，都是如此，所以孪生素数有无穷多。 学习数论一定要学透整除法，弄懂有限素数、公倍数、公倍数区间、素数倍数系、素数平方数等概念。弄懂孪生素数、孪生（奇）合数、孪生（奇）素（奇）合数概念，弄懂它们的来源。 学习数论一定还要知道乘数和加数的关系。非1奇数列3,5,7,9,…,d,d+2,…上的非1自然数都是素数2,3,5,…,P,…的乘积，也都是素数2,3,5,…,P,…的和。具体地说偶数6,8,10,…,e,e+2,…都是两个奇素数的和；奇数9,11,13,…,d,d+2,…都是三个奇素数的和。因为每一个奇素数P与奇素数序列3,5,7,11,…,P,…上等于大于它的奇素数依次循环相加P后全得到偶数6,8,10,…,e,e+2,…，所以每个偶6,8,10,…, e,e+2,…都是两个奇素数的和；因为每一个奇素数P与奇素数序列3,5,7,11,…,P,…上等于大于它的奇素数依次循环相加2P后全得到奇数9,11,13,…,d,d+2,…，所以每个奇素数9,11,13,…,d,d+2,…都是三个奇素数的和。 学习数论一定还要知道，素数平方数与其根的变化关系。在区间[2，p n·p n-1]内，未知素数p n+1,…,p n+S,是由已知有限素数2,3,5,…,p n倍数变化量决定的；在奇数区间[3，p n·p n-2]内，未知孪生素数(p f,p s)n+1,…决定于已知含有有限素数3,5,…, p f,p s倍数的孪生数的变化量。注：其(p f,p s)n是已知第n对儿孪生素数。 学习数论一定要学透整除法，素数变化关系，还要知道乘数和加数的关系就足够了。不要弃简（整除法）求繁（素数、孪生素数密度法）。 我们知道，可以有n个连续合数。这样我们可以取有同样个数的素数的x1 和x2，这样我们对x1和x2取对数（对x1和x2进行微积分运算也一样）后的值log x1，log x2却不一样。因此1/log x就失去了它的素数分布密度的意义了。亲爱的数论朋友们，觉悟吧！用素数定理方式、方法不能在无限大奇数、偶数上彻底证明相关素数问题！

素数定理随笔

素数定理随笔 SCIbird 本文献给数学大师高斯 本文试图介绍猜测素数定理的一种思路，以及简单的解析证明。尽管看起来有些事后诸葛亮的感觉，但确实是一种认识素数定理的途径，希望本文能够给读者以启迪。 约定p 始终代表素数，,z s 表示复数。记()x π表示不超过x 的素数的个数，所谓素数定理，指下面极限表达式 ()lim 1/ln x x x x π→∞= 本文主要围绕这个表达式来谈谈自己的一些心得体会。应该指出，上述结论已经有严格的数学证明（包括初等证明），但本文重点是给出一条探索素数的途径，文章中主要以近似和形式推导为主，大胆猜测，严格证明。 通过原始的数值计算来观察()x π的分布规律是常见的思维方法，见下表： 表格出自华罗庚的《数论导引》 其中，函数2Li ln x dt x t =∫（这是一个非初等积分）由高斯所发现，是()x π的另一个渐进表达式。由洛比达法则可知 Li lim 1/ln x x x x →∞=

函数li x 按如下方式定义 1001li lim ln x dt x t η ηη?→+????=+????∫∫ 显然Li li li 2x x =?. 从上表可以看出，利用li x 作为()x π的渐进函数，效果比/ln x x 要好一些，不过本文的主角其实是函数Li x . 素数作为整数的基础，自古以来备受数学家们的重视。首先，素数有无穷多个。其次，素数又非常少，即()/0x x π→. 第三，素数的分布似乎毫无规律，总的来看很稀疏，偶尔有集聚现象。 所以当人们证明()x π的极限情况有很简单的渐进表达式/ln x x 时，还是感到很神奇。据称，素数定理、费马大定理和哥德巴赫猜想是20世纪初数论中的三大著名猜想，而且素数定理当时的名气最大。 我们主要沿着高斯的发现途径Li x 来找到突破口，这里面也包含很多后来人的工作。与前人思路不同高斯不是简单研究()x π的数值分布特点，而是考察比值()/x x π的分布特点，猜测是否有简单函数()x ?来近似代替。 按数学家迪厄多内的说法，高斯考虑(,1000)x x +内的所有素数，通过大量的计算，高斯从数值表中观察到，当x 很大时，有下面的近似性质： (1000)()1000x x ππ+?正比于1ln x 数值计算表明，用Li x 来近似表示()x π，效果不错。 这一深刻的发现一方面包含高斯辛勤的计算劳动，同时体现了高斯的敏锐直觉。另一方面，直观上也不难理解高斯的发现，笔者当初第一感觉是高斯似乎在寻找素数分布的某种概率分布（笔者下意识想到了正态分布），正确地说，高斯是在寻找素数的某种密度函数分布（近似表达式）。 同一时期，法国数学家勒让德（此人数学上经常与高斯撞车）也发现了素数分布近似关系()~/(ln )x x x B π?，其中B 是一个常数。数学史上一般认为，勒让德和高斯是素数定理的“发现者”（他们没有给出数学证明）。

素数的分布规律

素数的分布规律 陈东平 浙江省丽水市中心医院323000 E-mail: chen12127@https://www.wendangku.net/doc/9711499502.html, MR 2010主题分类号：A11 中图分类号：O156.4 摘要：本文找到了素数在自然数中特殊的分布规律，并由此而解决了孪生素数的无限性难题。 关键词：规律素数孪生素数 素数在自然数中的分布是有规律的，找到这一规律能为我们系统地研究素数奠定坚实的基石。 1. 梅森素数 从梅森素数表中，我们发现，22-1=3, 23-1=7, 27-1=127 都是素数，并且，2127-1=A1也是素数，那么，2A1-1=A2是不是素数呢？A3又如何？下文中，我们将证明2, 3, 7, 127, A1, A2……这一组数，构成了素数在自然数中特殊的分布规律，因此，它们必然都是素数，诚如此，我们便论证了偶完全数的无限性。 证： 127≡-3 (mod 13) 因此，13│26+1

A1≡-3(mod 29) 因此，29│214+1 A2≡-3(mod 509) 因此，509│2254+1 A3≡-3(mod 4A1+1) 因此，4A1+1│22A1+1 …… 127≡-23-1(mod 17) [17= 22 )2 3(2- ?] 因此，17│24+1 A1≡-27-1(mod 97) 因此，97│224+1 A2≡-2127-1(mod 32257) 因此，32257│28064+1 …… 24≡2（mod 7） （7=32-2） 因此，7│23-1 224≡2（mod 47） 因此，47│223-1 28064≡2（mod 16127）因此，16127│28063-1 ……

求素数算法

求素数的算法及其复杂度分析 关于素数的算法是信息学竞赛和程序设计竞赛中常考的数论知识，在这里我跟大家讲一下寻找一定范围内素数的几个算法。看了以后相信 对大家一定有帮助。 正如大家都知道的那样，一个数n 如果是合数，那么它的所有的因子不超过sqrt(n)--n的开方,那么我们可以用这个性质用最直观的方法 来求出小于等于n的所有的素数。 num = 0; for(i=2; i<=n; i++) { for(j=2; j<=sqrt(i); j++) if( j%i==0 ) break; if( j>sqrt(i) ) prime[num++] = i; //这个prime[]是int型，跟下面讲的不同。 } 这就是最一般的求解n以内素数的算法。复杂度是 o(n*sqrt(n))，如果n很小的话，这种算法（其实这是不是算法我都怀疑，没有水平。当然没 接触过程序竞赛之前我也只会这一种求n以内素数的方法。-_-~）不会耗时很多. 但是当n很大的时候，比如n=10000000时，

n*sqrt(n)>30000000000,数量级相当大。在一般的机子它不是一秒钟跑不出结果，它是好几分钟都跑不 出结果，这可不是我瞎掰的，想锻炼耐心的同学不妨试一试~。。。。 在程序设计竞赛中就必须要设计出一种更好的算法要求能在几秒钟甚至一秒钟之内找出n以内的所有素数。于是就有了素数筛法。 （我表达得不清楚的话不要骂我，见到我的时候扁我一顿我不说一句话。。。） 素数筛法是这样的： 1.开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false. 2.然后： for( i=3; i<=sqrt(n); i+=2 ) { if(prime[i]) for( j=i+i; j<=n; j+=i ) prime[j]=false; } 3.最后输出bool数组中的值为true的单元的下标，就是所求的n以内的素数了。 原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i