爱华网质数(素数)
一、质数基本概念
质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数。换句话说，只有两个正因数（1和自己）的自然数即为素数。比1大但不是素数的数称为合数。1和0既非素数也非合数。
素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个正整数的乘积。
例如，15＝3×5，所以15不是素数；又如，12＝6×2＝4×3，所以12也不是素数。另一方面，13除了等于13×1以外，不能表示为其它任何两个正整数的乘积，所以13是一个素数。
最小的素数是2，它也是唯一的偶素数。最前面的素数依次排列为：2，3，5，7，11，13，17，......
不是质数且大于1的正整数称为合数。
二、算术基本定理
任何大于1的正整数n可以唯一表示成有限个素数的乘积:n=p_1p_2...p_s, 这里p_1≦p_2 ≦...≦p_s是素数。
这一表达式也称为n的标准分解式。
算术基本定理是初等数论中最基本的定理。由此定理，我们可以重新定义两个整数的最大公因子和最小公倍数等等概念。
1不能称作素数，是因为要确保算术基本定理所要求的唯一性成立。
三、质数分布问题
就是指素数在正整数集或其特殊子集中的分布情况，比如素数个数问题等等。这方面的结果如下;
（1）欧几里得以反证法证明了素数个数无限；欧拉利用解析方法证明了此结论。
（2）高斯提出著名的素数定理（当时是猜想，后被证明）：设π(x)是不超过x的素数个数，那么极限(x趋向于无穷)limπ(x)/(x/Ln x)=1更好的逼近公式有高斯提出的li(x)函数， 即lim π(x)/lix=1。
（3）狄利克雷证明了任何等差数列： a, a+d,a+2d,...a+nd,...(这里a,d互质)中都包含无限个素数
（4）兰伯特猜想（已被证明）：在n和2n之间必定存在一个素数，这里n是大于1的正整数。
十亿以内素数分布及概率
"10" |4 |40%
“100” |25 |25%
“1000” |168|16.8%
“10000” |1229|12.29%
“100000” |9592|9.592%
“1000000” |78498|7.8498%
“2000000” |148933|7.44665%
“10000000” |664579|6.64579%
“100000000” |5761455|5.761455%
“200000000” |11078937|5.5394685%
“300000000” |16252325|5.41744167%
“400000000” |21336336|5.334084%
“500000000” |26355877|5.2711754%
“600000000” |31324713 |5.2207855%
“700000000” |36252941|5.17899157%
“800000000” |41146189|5.143273625%
“900000000” |46009225|5.1121361%
“1000000000” |50847544|5.0847544%
可以看出，越往后质数比例愈小，但总数却是增多，
可以看出素数的个数是无限的，这一结论已经被古希腊数学家欧几里得在其著作《几何原本》中用反证法证明。
四、质数构造问题
如何构造素数，即寻找一个可以只产生素数的公式，是古典数论的一个重要课题。许多数学家曾经尝试过此问题。以下列举一些经典的例子。
（1）费马定义了费马数F_n=2^(2^n)+1.他猜测费马数都是素数。但是欧拉证明了641能够整除F_5,目前为止，人们还不能证明是否有无限个费马数是素数。有猜测认为，几乎所有费马数都是合数。
（2）高斯证明，一个正n边形可以用尺规作图得到的充要条件是：n的所有奇素因子都是费马素数。特别地，正十七边形可以用尺规做出。
（3）梅森定义了M_p=2^p-1.他猜测当p是素数时，M_p也是素数,称为梅森素数。但这一结论也被否定了。一个重要问题是：是否有无限个梅森素数？此猜想至今未被证明。
（4）一个数n是偶完全数当且仅当n可以写为n=2^{p-1}M_p, 这里p和梅森数M_p都是素数。一个重要问题是：是否存在奇完全数？
（5）欧拉和费马等人构造了一些多项式，在一定范围内都取值素数，比如：f(n)=n^2-n+41,在n=1,2,...,40时都是素数。一个有趣问题是：存在无穷个素数可以写为n^2+1的形式.
（6）只产生素数的公式很容易构造，但它们是没有理论意义的。比如令B_n=((n-1)!+1)/n,用{x}表示x小数部分，[x]表示x的整数部分。于是函数f(n)=n+(n-2)[{-B_n}]只产生素数。这是利用了著名的威尔逊定理, 即"n是素数当且仅当 (n-1)!+1能被n整除"。
（7）传统筛法是利用一条定理：“n不能够被不大于根号n的任何素数整除，则n是一个素数”。
五、质数趣味性质
1.质数的一般表达式?
(Euler)p=x^2+x+41 x=0...39
又如:p=6x^2+6x+31x=0...28
p=x^2-79x+1601x=0...79
p=x^2-2999x+2248541x=1460...1539
.........
2.质数判定:
(Wilson): 当且仅当 (N-1)!+1 能被 N 整除时, N 为质数;
(Lucas) : 若 a^x-1 于x=N-1 时能被 N 整除,而 x 为 N-1之正因子又不能被 N 整除,则 N 为质数;
......
3.由顺(逆)序数字构成的质数:
23 , 67 , 89 , 4567 , ...., 23456789 , 1234567891 ,...
1234567891234567891234567891...
43 , 76543 ....
4.回文质数:
11 , 101 , 131 , 151 ,181 , 191 ,313 ,353 ,373 , 383 ,727 ,757 ,787,919 ,929...
回方质数对:
(181 191) (373383) (787 797) (919929) (1050110601) (11311 11411)
(12721 12821)(13831 13831)(15451 15551)(16561 16661)(30103 30203)....
5.可逆质数:
(13 31)(17 71) (3773) (79 97)(107 701)
145315591583987654301 ..........
6.孪生质数:
(3 5)(5 7) (1113).................(9677 9678)
(Slememt) :当且仅当 4[(n-1)!+1]+n =O[modn(n+2)] 时 n 与n+2 形成一对孪生质数;
.......
7.形成级数的质数:
7 37 6797 127 157
7 157 307457 607757 907
71238146917001931111621 13931
107137 167197227 257
1994096198291039 12491459 16691879 2089
(Dirichlet):若d>=0a<>0 是2个互质的正整数,那么 a, a+d ,a+2d ....包含无穷多个质数;
.....
8.质数的倒数:
1/3=0.333.....(3)...
1/7=0.142857...(142857)...
1/11=0.0909...(09)...
1/13=0.076923...(076923)....
1/17=0.0588235294117647...(0588235294117647)...
....
六、质数各类猜想
上面我们已经提及了几类猜想，如梅森素数无限的猜想，费马素数有限的猜想等等。以下列举其他一些重要猜想。
（1）黎曼猜想
黎曼通过研究发现，素数分布的绝大部分猜想都取决于黎曼zeta函数ζ（s）的零点位置。他猜测那些非平凡零点都落在复平面中实部为1/2的直线上，这就是被誉为千禧年世界七大数学难题之一的黎曼猜想，是解析数论的重要课题。
（2）孪生素数猜想
如果p和p+2都是素数，那么就称他们为孪生素数。一个重要的问题就是：是否存在无限多对孪生素数？这一问题至今没有突破性进展。
（3）哥德巴赫猜想（GoldbachConjecture)
（a）不小于6的偶数，都可表示为两个奇素数之和(一般用代号“1+1”表示)。
（b）每个不小于9的奇数都可以表示为三个奇素数之和。
问题的第二部分，利用解析数论中的圆法估计，已被证明。困难的是第一部分。
哥德巴赫猜想是德国数学家哥德巴赫（C．Goldbach，1690-1764）于1742年6月7日在给大数学家欧拉的信中提出的，所以被称作哥德巴赫猜想。同年6月30日，欧拉在回信中认为这个猜想可能是真的，但他无法证明。从此，这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。
18、19世纪，所有的数论专家对这个猜想的证明都没有作出实质性的推进，直到20世纪才有所突破。直接证明哥德巴赫猜想不行，人们采取了“迂回战术”，就是先考虑把偶数表为两数之和，而每一个数又是若干素数之积，被称为“殆素数”意思是很像素数。如果把命题"每一个大偶数可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a＋b"，那么哥氏猜想就是要证明"1＋1"成立。
哥德巴赫猜想至今没有任何实质性进展。
七、质数表
1000以内：
2 3 5 7 11 13 17 19 2329
31 37 41 43 47 53 59 61 6771
73 79 83 89 97 101 103 107 109113
127 131 137 139 149 151 157 163167 173
179 181 191 193 197 199 211 223227 229
233 239 241 251 257 263 269 271277 281
283 293 307 311 313 317 331 337347 349
353 359 367 373 379 383 389 397401 409
419 421 431 433 439 443 449 457461 463
467 479 487 491 499 503 509 521523 541
547 557 563 569 571 577 587 593599 601
607 613 617 619 631 641 643 647653 659
661 673 677 683 691 701 709 719727 733
739 743 751 757 761 769 773 787797 809
811 821 823 827 829 839 853 857859 863
877 881 883 887 907 911 919 929937 941
947 953 967 971 977 983 991 997(168个)
