素数是什么 c语言素数是什么 _生活百科

文章插图
素数是什么1
1、质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数。
2、质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，pn，设N=p1乘p2乘pn，那么，是素数或者不是素数。如果为素数，则要大于p1，p2，pn，所以它不在那些假设的素数集合中。
数论之素数计数2这是一系列关于数论的介绍性文章，目的在于推广数学知识，拓展读者的数学思维。至于为什么用图文而不是视频？图文有三个优越性：一是图文数据量小，节省学习时间；二是有助于个人主动思考；三是文字里的关键字，可以方便读者查阅相关资料。
有多少个素数呢？我们已知存在无穷多个素数，也存在无穷多个合数，哪个更多？尽管这两种数都有无穷多个，我们仍可使用计数函数比较它们。
首先，从能说明基本思想的比较容易的问题着手，拿偶数来试验、发现规律，直觉告诉我们近一半数是偶数。通过观察偶数计数函数
需要将这种直觉建立在坚实的基础之上，上述E(x)表示不超过x的正偶数个数，
例如，
E(3) = 1，E(4) = 2， E(5) = 2，...，E(100) = 50，E(101) = 50,...
考察比率E(x)/x:
比率E(x)/x总是等于1/2肯定不成立，但是当x很大时， E(x)/x接近于1/2是成立的。如果了解一点微积分知识，你会意识到我们在设法说明
这个陈述恰说明x越来越大时E(x)/x与1/2间的距离越来越接近于0 。
对素数做相同的事情。素数计数函数被称为:
例如= 4,这是因为小于10的素数是2, 3,5,7 。下表给出了(x)与比率n(x)/x的值。
x
10
50
100
200
500
1000
5000
4
15
25
46
95
168
669
0.400
0.300
0.250
0.230
0.190
0.168
0.134
似乎x越来越大时n(x)/x越来越小，假设这种模式继续下去，我们会说“大多数整数不是素数”，这就进一步提出n(x)/x以怎样的速度减小的问题。下述著名结果给出答案，它是19世纪数论取得的最高成就之一。
定理 (素数定理)当x很大时，小于x的素数个数近似等于x/In(x)，即
In(x)(称为x的自然对数)是以e=2.718 2818…为底x的对数。下面是比较n(x)与x/In(x)值的表:
x
10
100
1000
4
25
168
1229
78498
50847534
4.34
21.71
144.76
1085.74
72382.41
48254942.43
0.921
1.151
1.161
1.132
1.084
1.054
简史大约在1800年通过检查类似的但比较短的表，高斯与勒让德独立地提出素数定理成立的猜想，几乎过去一个世纪还没有人加以证明。1896年阿达马(Jacques Hadamard)与Ch. dela vallée Poussin各自努力去证明素数定理。正如狄利克雷定理的证明要用复分析方法(即复变函数论)一样，在1948年埃德斯(Paul Erd?s)与塞尔伯格(Atle Selberg)发现了素数定理的“初等”证明，他们的证明是初等的仅指不需要复分析方法，并不意味着容易。
使人有点惊讶的是证明有关整数的定理，如狄利克雷定理与素数定理，数学家不得不使用微积分作为工具，被称为解析数论的数学分支专用微积分方法证明数论定理。
表格在发现规律时的重要性。
有许多著名的涉及素数的未解问题,我们在此叙述三个这样的问题及其简史。
猜想 (哥德巴赫猜想) 每个偶数可表示成两个素数之和。
哥德巴赫在1742年7月7日给欧拉的一封信中提出这个猜想，不难验证哥德巴赫猜想对前几个偶数成立，例如，
4 = 2 +2, 6 = 3 +3, 8 = 3 +5, 10 = 3 +7, 12 = 5 +7,
14 = 3 + 11, 16 = 3 + 13, 18 = 5 + 13, 20 = 7 + 13,.
这就对直到20的偶数验证了哥德巴赫猜想,使用计算机人们已对以下的偶数验证了哥德巴赫猜想，数学家甚至能够证明与哥德巴赫猜想相似的结论，这是支持哥德巴赫猜想的有力证据。1937年,维诺格拉朵夫(I. M. Vinogradov)证明了每个充分大的奇数n可表成三个素数之和。1966年,陈景润证明了每个充分大的偶数可表成p+a的形式,其中p是素数, a是素数或两个素数的乘积。
猜想 (孪生素数猜想) 存在无穷多个素数p使得p+2也是素数.
素数很不规则，相邻两个素数间常常会有很大的间隙。例如，素数370261之后紧接着111个合数。然而，也有很多素数p紧随另一个素数p+2 。这些数对被称为孪生素数。孪生素数猜想说明孪生素数表没有结束，前几个李生素数是(3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73),(101,103) (107,109), (137,139), (149,151), (179,181), (191,193),(197,199), (227 ,229), (239,241), (269,271), (281,283), (311,313).