网站地图
质数

质数(prime number)又称素数,有无限个。

质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。

质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。

质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法:反证法。具体证明如下:假设质数只有有限的n个,从小到大依次排列为p1,p2,……,pn,设N=p1×p2×……×pn,那么,

如果

如果 为合数,因为任何一个合数都可以分解为几个素数的积;而N和N+1的最大公约数是1,所以不可能被p1,p2,……,pn整除,所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数,都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说,素数有无穷多个。

其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的,恩斯特库默的证明更为简洁,哈里弗斯滕伯格则用拓扑学加以证明。

分布规律

以36N(N+1)为单位,随着N的增大,素数的个数以波浪形式渐渐增多。

孪生质数也有相同的分布规律。

以下15个区间内质数和孪生质数的统计数。

S1区间172,有素数18个,孪生素数7对。(2和3不计算在内,最后的数是孪中的也算在前面区间。)

S2区间73216,有素数27个,孪生素数7对。

S3区间217432,有素数36个,孪生素数8对。

S4区间433720,有素数45个,孪生素数7对。

S5区间7211080,有素数52个,孪生素数8对。

S6区间10811512,素数60个,孪生素数9对。

S7区间15132016,素数65个,孪生素数11对。

S8区间20172592,素数72个,孪生素数12对。

S9区间25933240,素数80个,孪生素数10对。

S10区间32413960,素数91个,孪生素数18对。

S11区间39614752素数92个,孪生素数17对。

S12区间47525616素数98个,孪生素数13对。

S13区间56176552素数108个,孪生素数14对。

S14区间65537560素数113个,孪生素数19对。

S15区间75618640素数116个,孪生素数14对。

素数分布规律的发现,许多素数问题可以解决。

尽管整个素数是无穷的,仍然有人会问“100,000以下有多少个素数?”,“一个随机的100位数多大可能是素数?”。素数定理可以回答此问题。

在一个大于1的数a和它的2倍之间(即区间(a, 2a]中)必存在至少一个素数。

存在任意长度的素数等差数列。

一个偶数可以写成两个合数之和,其中每一个合数都最多只有9个质因数。(挪威数学家布朗,1920年)

一个偶数必定可以写成一个质数加上一个合成数,其中合数的因子个数有上界。(瑞尼,1948年)

一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来,有人简称这结果为 (1 + 5)(中国潘承洞,1968年)

一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 (1 + 2)

质数具有许多独特的性质:

(1)质数p的约数只有两个:1和p。

(2)初等数学基本定理:任一大于1的自然数,要么本身是质数,要么可以分解为几个质数之积,且这种分解是唯一的。

(3)质数的个数是无限的。

(4)质数的个数公式

(5)若n为正整数,在

(6)若n为大于或等于2的正整数,在n到

(7)若质数p为不超过n(

(8)所有大于10的质数中,个位数只有1,3,7,9。

根据

构造函数

根据1-1 性质 以多项式

为函数

当 n 为素数或 1 时,

得素数密度公式

式中 1 定义为素数

素数及伪素数通项公式

把它拓展到实数那么它的切线为:

由切线方程知,素数永远在斜率3的折线上摆动,最大斜率3+

素数的变量n的通项公式

有以上公式能够确定伪素数及素数,那么通过对其变量n的识别,我们可以写出任意素数或伪素数

先确定伪素数的变量n,用n(x,y)来表示它,变量是个三维变量,公式如下:

n为偶数时:x,y 均自然数

n为奇数时:

满足以上条件时是P(n)为素数。excel vba 素数输出程序详见素数公式词条。

质数被利用在密码学上,所谓的公钥就是将想要传递的信息在编码时加入质数,编码之后传送给收信人,任何人收到此信息后,若没有此收信人所拥有的密钥,则解密的过程中(实为寻找素数的过程),将会因为找质数的过程(分解质因数)过久,使即使取得信息也会无意义。

在汽车变速箱齿轮的设计上,相邻的两个大小齿轮齿数设计成质数,以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数,可增强耐用度减少故障。

在害虫的生物生长周期与杀虫剂使用之间的关系上,杀虫剂的质数次数的使用也得到了证明。实验表明,质数次数地使用杀虫剂是最合理的:都是使用在害虫繁殖的高潮期,而且害虫很难产生抗药性。

以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。

多数生物的生命周期也是质数(单位为年),这样可以最大程度地减少碰见天敌的机会。

在一般领域,对正整数n,如果用2到

质数大于等于2 不能被它本身和1以外的数整除

Python 代码:

Java代码:

Php代码:

C#代码:

C代码:

C/C++代码:

Pascal代码:

Javascript代码:

Go代码:

Basic 代码

ALGOL代码

上下素性判决定法

首先,本文英文字母都表示整数,上半部B 》3N 》W,下半部B 》W 》3N。大于3的素数只有6N-1和6N+1两种形式,我们只需判定这两种数是素数还是合数即可。

命题 1 对于B=36N+1 型数而言。

若不定方程

则 6(3N-W)+1 是小因子数;6(3N+W)+1 是大因子数。

若不定方程

则 6(3N-W)-1 是小因子数;6(3N+W)-1 是大因子数。

两式都无解,是素数。

命题 2对于B=36N+7 形数而言。

若不定方程

则 6(3N-W)+1 是小因子数,6(3N+W+1)+1 是大因子数。

若不定方程

则 6(3N+2-W)-1 是小因子数,6(3N+W+3)-1 是大因子数。

两式都无解,是素数。

命题 3对于B=36N+13 形数而言。

若不定方程

则 6(3N+1-W)+1 是小因子数,6(3N+1+W)+1是大因子数。

若不定方程

则 6(3N+2-W)-1 是小因子数,6(3N+2+W)-1是大因子数。

两式都无解,是素数。

命题 4 对于B=36N+19 形数而言。

若不定方程

则 6(3N+1-W)+1 是小因子数;6(3N+2+W)+1 是大因子数。

若不定方程

则 6(3N+1-W)-1 是小因子数;6(3N+2+W)-1 是大因子数。

两式都无解,是素数。

命题 5 对于B=36N+25 形数而言。

若不定方程

则 6(3N+2-W)+1 是小因子数,6(3N+2+W)+1 是大因子数。

若不定方程

则 6(3N+1-W)-1 是小因子数,6(3N+1+W)-1 是大因子数。

两式都无解,是素数。

命题 6 对于B=36N+31 形数而言。

若不定方程

则 6(3N+2-W)+1 是小因子数,6(3N+3+W)+1是大因子数。

若不定方程

则 6(3N-W)-1 是小因子数,6(3N+1+W)-1是大因子数。

两式都无解,是素数。

命题 7对于B=36N-1 形数而言。

若不定方程

则 6(3N-W)+1 是小因子数;6(3N+W)-1 是大因子数。

若不定方程

则 6(W-3N)-1 是小因子数;6(W+3N)+1 是大因子数。

两式都无解,是素数。

命题 8对于B=36N+5 形数而言。

若不定方程

则 6(W-3N)+1 是小因子数,6(W+3N+1)-1 是大因子数。

若不定方程

则 6(W-3N-2)-1 是小因子数,6(W+3N+3)+1 是大因子数。

两式都无解,是素数。

命题 9对于B=36N+11 形数而言。

若不定方程

则 6(W-3N-1)+1 是小因子数,6(W+3N+1)-1是大因子数。

若不定方程

则 6(W-3N-2)-1 是小因子数,6(W+3N+2)+1是大因子数。

两式都无解,是素数。

命题 10 对于B=36N+17 形数而言。

若不定方程

则 6(W-3N-1)+1 是小因子数;6(W+3N+2)-1 是大因子数。

若不定方程

则 6(W-3N-1)-1 是小因子数;6(W+3N+2)+1 是大因子数。

两式都无解,是素数。

命题 11 对于B=36N+23 形数而言。

若不定方程

则 6(W-3N-2)+1 是小因子数,6(W+3N+2)+1 是大因子数。

若不定方程

则 6(W-3N-1)-1 是小因子数,6(W+3N+1)+1 是大因子数。

两式都无解,是素数。

命题 12 对于B=36N+29 形数而言。

若不定方程

则 6(W-3N-2)+1 是小因子数,6(W+3N+3)-1是大因子数。

若不定方程

则 6(W-3N)-1 是小因子数,6(W+3N+1)+1是大因子数。

两式都无解,是素数。

素性检测一般用于数学或者加密学领域。用一定的算法来确定输入数是否是素数。不同于整数分解,素性测试一般不能得到输入数的素数因子,只说明输入数是否是素数。大整数的分解是一个计算难题,而素性测试是相对更为容易(其运行时间是输入数字大小的多项式关系)。有的素性测试证明输入数字是素数,而其他测试,比如米勒 - 拉宾(MillerRabin )则是证明一个数字是合数。因此,后者可以称为合性测试。

素性测试通常是概率测试(不能给出100%正确结果)。这些测试使用除输入数之外,从一些样本空间随机出去的数;通常,随机素性测试绝不会把素数误判为合数,但它有可能为把一个合数误判为素数。误差的概率可通过多次重复试验几个独立值a而减小;对于两种常用的测试中,对任何合数n,至少一半的a检测n的合性,所以k的重复可以减小误差概率最多到

随机素性测试的基本结构:

1.随机选取一个数字a。

2.检测某个包含a和输入n的等式(与所使用的测试方法有关)。如果等式不成立,则n是合数,a作为n是合数的证据,测试完成。

3.从1步骤重复整个过程直到达到所设定的精确程度。

在几次或多次测试之后,如果n没有被判断为合数,那么我们可以说n可能是素数。

常见的检测算法:费马素性检验(Fermat primality test),米勒拉宾测试(MillerRabin primality test) ,SolovayStrassen测试,卢卡斯-莱默检验法(LucasLehmer primality test)。

筛素数法可以比枚举法节约极大量的时间(定n为所求最大值,m为≤n的质数个数,那么枚举需要O(n^2)的时间复杂度,而筛素数法为O(m*n),显然m<<n,所以时间效率有很大提升。)。如1000000的数据范围,用筛素数法可在2s内解决。

思路:建立一个bool型数组M,若已知一个数M[k]是质数,那么其i(i为正整数)倍M[k*i]必然为合数,可将其去除。

筛选法的Java实现,如下:

采用简单的埃氏筛选法和简单的开方判断素数法计算1000000以内素数的个数的效率比较:

StopWatch '计算1000000以内素数的个数': running time (millis) = 268

-----------------------------------------

ms % Task name

-----------------------------------------

00024 009% 简单的埃氏筛选法

00244 091% 简单的开方判断素数法

哥德巴赫猜想:是否每个大于2的偶数都可写成两个素数之和?

孪生素数猜想:孪生素数就是差为2的素数对,例如11和13。是否存在无穷多的孪生素数?

斐波那契数列内是否存在无穷多的素数?

是否有无穷多个的梅森素数?

在n2与(n+1)2之间是否每隔n就有一个素数?

是否存在无穷个形式如X2+1素数?

黎曼猜想

关键词:完全不等数,SN区间,LN区间.

大于3的素数只分布在6n-1和6n+1两数列中。(n非0自然数,下同)

6n-1数列中的合数叫阴性合数,其中的素数叫阴性素数。

6[6NM+(M-N)]-1=(6N+1)(6M-1)(N M两个非0自然数,N=〈 M,下同)

6[6NM-(M-N)]-1=(6N-1)(6M+1)

在6n-1数列中只有这两种合数,余下就是阴性素数了,所以就有阴性素数定理

6NM+-(M-N)=/=x(阴性不等数)

6x-1=q(阴性素数)

6n+1数列中的合数叫阳性合数,其中的素数叫阳性素数。

6[6NM+(N+M)]+1=(6N+1)(6M+1)

6[6NM-(N+M)]+1=(6N-1)(6M-1)

在6n+1数列中只有这两种合数,余下就是阳性素数了,所以就有阳性素数定理

6NM+-(N+M)=/=X(阳性不等数)

6X+1=P(阳性素数)

完全不等数(X),它既不等于阴性上下两式;也不等于阳性上下两式。

(X)=/=6NM+-(M+-N)

则有6(X)+1=P 6(X)-1=q (p减1能被6整除的素数,q加1能被6整除的素数,下同)

一个完全不等数所产生的阴性素数q和阳性素数P就是一对孪生素数.

并且完全不等数与孪生素数是一一对应的.

四。阴阳四种等数在自然数列中的分概况

6NM+(M-N)=阴性上等数6NM-(M-N)=阴性下等数

6NM+(N+M)=阳性上等数6NM-(N+M)=阳性下等数

为了搞清它们在自然数中分布情况,把四式中的N叫级别因子数,M叫无限因子数。

四种等数的每一个级别的最小等数都在6NN+-(N+N)范围。

每一级别的上等数相邻两等数距离是6n+1,在自然数列中比例是1/(6n+1),两种上等数每个级别的比例合计是2/(6n+1),(但实际是略少于这个比例因每一级别的底部都没有这个级别的上等数;下等数也一样的情况。)

每一级别的下等数相邻等数的距离是6n-1,在自然数列中的比例是1/(6n-1),阴阳两种下等数的每个级别的合计比例是2/(6n-1)。

每个级别的四种等数在自然数列中的比例是24N/[(6N+1)(6N-1)].

五。四种等数大小数列的互相渗透

自然数列中有阴性上等数数列,阴性的下等数数列,阳性上等数数列和阳性下等数数列。它们的级别有无限多,每一个级别的数列的等数都是无限多的。同一种等数级别不同的数列都是互相渗透而产生重叠,并以两级别的等数距离的乘积而严格地重叠的。在计算一种若干的级别的等数时用连乘式正好可以表示它的渗透重叠关系。四种等数数列之间都有互相渗透而重叠,只有同一级别阴阳上上数列.下下数列没有渗透.四种数列之间的渗透重叠不用计算也足够可以证明了。

六。与素数分布基本同步的SN区间

把自然数划分成12,24,36……以12为递增的一个个区间,这样的区间叫SN区间。SN区间与四种等数数列是同步的,即:

12(1+2+3+……+N)=6NN+6N

在这样的区间内包括N级别及以下的所有四种等数数列的等数,并没有比N级别大的数列等数,与四种等数的级别是完全同步的,所以与素数的分布也是同步的。

七。每个大于S8区间内都有8个以上的完全不等数

在每一个SN区间只有存在1至N级别的四种数列等数,每一级别等数的比例是可以确定,由于上下级别的渗透。就可以拿以下式来计算S8区间的完全不等数的至少个数。

12*8*11/35*95/143*251/323*479/575*779/899*1151/1295*1593/1763*2111/2303=8.2768

其他每一个SN区间可用这种方法计算.

随着区间的增大完全不等数计算的数量也会越来越多.以后都会超过8个.

用最严格下取整的误差分析方法,将SN区间捆绑成1,2,4,8,16......2^(N-1)的LN区间.在每一个大于S8的SN区间计算都大于8个完全不等数,在每一个LN区间都有2^N-1级别等数数列, 每级级别有4种等数数列,每一级别一种等数筛一次误差极限是1 .每一个LN区间误差极限是4*(2^N-1).

8*2^(N-1)-4*(2^N-1)=4

最严格下取整后大于L4的区间仍然还有4个完全不等数。

根据以上的论证,在大于S8区间每一个SN区间都有8个以上的完全不等数.

严格的下取整后,大于L4的每一个LN区间都还有多于4个的完全不等数以上的量。

LN区间是无限多的,完全不等数与孪生素数对是一一对应的,所以孪生素数也是无限多的。

这个证明期待着权威的表态。

哥德巴赫猜想证明的困难在于,任何能找到的素数,在以下式中都是不成立的。2*3*5*7*。。。。。。*PN*P=PN+(2*3*5*7*。。。。。。*P-1)*PN前面的偶数减去任何一个素数PN的差必是合数.

在1742年给欧拉的信中哥德巴赫提出了以下猜想:任一大于2的整数都可写成两个质数之和。因现今数学界已经不使用“1也是素数”这个约定,原初猜想的现代陈述为:任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一等价版本,即任一大于2的偶数想陈述为欧拉的版本。把命题"任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"。1966年陈景润证明了"1+2"成立,即"任一充分大的偶数都可以表示成二个素数的和,或是一个素数和一个半素数的和"。 今日常见的猜想陈述为欧拉的版本,即任一大于2的偶数都可写成两个素数之和,亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。

从关于偶数的哥德巴赫猜想,可推出任一大于7的奇数都可写成三个质数之和的猜想。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。

若关于偶数的哥德巴赫猜想是对的,则关于奇数的哥德巴赫猜想也会是对的。1937年时前苏联数学家维诺格拉多夫已经证明充分大的奇质数都能写成三个质数的和,也称为“哥德巴赫-维诺格拉朵夫定理”或“三素数定理”。2013年,秘鲁数学家哈拉尔德赫尔弗戈特在巴黎高等师范学院宣称:证明了一个“弱哥德巴赫猜想”,即“任何一个大于7的奇数都能被表示成3个奇素数之和”。

黎曼猜想是关于黎曼ζ函数ζ(s)的零点分布的猜想,由数学家波恩哈德黎曼(1826~1866)于1859年提出。德国数学家希尔伯特列出23个数学问题。其中第8问题中便有黎曼假设。素数在自然数中的分布并没有简单的规律。黎曼发现素数出现的频率与黎曼ζ函数紧密相关。黎曼猜想提出:黎曼ζ函数ζ(s)非平凡零点(在此情况下是指s不为-2、-4、-6等点的值)的实数部份是1/2。即所有非平凡零点都应该位于直线1/2 + ti(“临界线”(critical line))上。t为一实数,而i为虚数的基本单位。无人给出一个令人信服的关于黎曼猜想的合理证明。

在黎曼猜想的研究中,数学家们把复平面上 Re(s)=1/2 的直线称为 critical line。 运用这一术语,黎曼猜想也可以表述为:黎曼ζ 函数的所有非平凡零点都位于 critical line 上。

黎曼猜想是黎曼在 1859 年提出的。在证明素数定理的过程中,黎曼提出了一个论断:Zeta函数的零点都在直线Res(s) = 1/2上。他在作了一番努力而未能证明后便放弃了,因为这对他证明素数定理影响不大。但这一问题仍然未能解决,甚至于比此假设简单的猜想也未能获证。而函数论和解析数论中的很多问题都依赖于黎曼假设。在代数数论中的广义黎曼假设更是影响深远。若能证明黎曼假设,则可带动许多问题的解决。

1849年,波林那克提出孪生质数猜想(the conjecture of twin primes),即猜测存在无穷多对孪生质数。猜想中的“孪生”是指一对质数,它们之间相差2。例如3和5,5和7,11和13,10,016,957和10,016,959等等都是孪生质数。

英国数学家戈弗雷哈代和约翰李特尔伍德曾提出一个“强孪生素数猜想”。这一猜想不仅提出孪生素数有无穷多对,而且还给出其渐近分布形式。2013年5月14日,《自然》(Nature)杂志在线报道张益唐证明了“存在无穷多个之差小于7000万的素数对”,这一研究随即被认为在孪生素数猜想这一终极数论问题上取得了重大突破,甚至有人认为其对学界的影响将超过陈景润的“1+2”证明。

36N(N+1)+ -1形的孪生素数,N《100000000 有109128对。

17世纪还有位法国数学家叫梅森,他曾经做过一个猜想:当2p-1 中的p是质数时,2p-1是质数。他验算出:当p=2、3、5、7、17、19时,所得代数式的值都是质数,后来,欧拉证明p=31时,2p-1是质数。 p=2,3,5,7时,2p-1都是素数,但p=11时,所得2,047=23×89却不是素数。

梅森去世250年后,美国数学家科尔证明,267-1=193,707,721×761,838,257,287,是一个合数。这是第九个梅森数。20世纪,人们先后证明:第10个梅森数是质数,第11个梅森数是合数。质数排列得杂乱无章,也给人们寻找质数规律造成了困难。

迄今为止,人类仅发现49个梅森质数。美国中央密苏里大学于2016年1月7日发现的质数,为迄今发现的最大质数,同时是一个梅森质数。由于这种质数珍奇而迷人,它被人们称为“数学珍宝”。值得一提的是,中国数学家和语言学家周海中根据已知的梅森质数及其排列,巧妙地运用联系观察法和不完全归纳法,于1992年正式提出了梅森素质分布的猜想,这一重要猜想被国际上称为“周氏猜测”。

(GIMPS)项目于2016年1月7日找到人类已知的最大素数274,207,281-1,该素数有22,338,618位,是第49个梅森素数。


相关文章推荐:
素数 | 因数 | 合数 | 欧几里得 | 几何原本 | 反证法 | 合数 | 集合 | 黎曼函数 | 哈里弗斯滕伯格 | 拓扑学 | 孪生质数 | 素数定理 | 挪威 | 瑞尼 | 潘承洞 | 无限 | 正整数 | 素数公式 | 密码学 | 公钥 | 密钥 | 分解质因数 | 变速箱 | 齿轮 | 鱼雷 | 生命周期 | 费马素性检验 | 卢卡斯-莱默检验法 | 哥德巴赫猜想 | 孪生素数猜想 | 斐波那契数列 | 梅森素数 | 黎曼猜想 | 欧拉 | 哥德巴赫 | 整数 | 等价 | 偶数 | 陈景润 | 半素数 | 哥德巴赫 | 弱哥德巴赫猜想 | 奇数 | 哥德巴赫猜想 | 前苏联 | 维诺格拉多夫 | 秘鲁 | 黎曼 | 波恩哈德黎曼 | 黎曼假设 | 实数 | 临界线 | 虚数 | 黎曼 | 素数定理 | 解析数论 | 黎曼假设 | 代数数论 | 波林 | 孪生质数 | 孪生 | 孪生素数猜想 | 梅森 | 科尔 | 周海中 | 周氏猜测 | GIMPS |
相关词汇词典