|
简介
就是在所有比1大的整数中，除了1和它本身以外，不再有别的约数，这种整数叫做质数，质数又叫做素数。这终规只是文字上的解释而已。能不能有一个代数式，规定用字母表示的那个数为规定的任何值时，所代入的代数式的值都是质数呢？ 质数的分布是没有规律的，往往让人莫名其妙。如：101、401、601、701都是质数，但上下面的301（7*43）和901（17*53）却是合数。 有人做过这样的验算：1^2+1+41=43,2^2+2+41=47,3^2+3+41=53……于是就可以有这样一个公式：设一正数为n，则n^2+n+41的值一定是一个质数。这个式子一直到n=39时，都是成立的。但n=40时，其式子就不成立了，因为40^2+40+41=1681=41*41。 被称为“17世纪最伟大的法国数学家”费尔马，也研究过质数的性质。他发现，设Fn=2^(2^n)，则当n分别等于0、1、2、3、4时，Fn分别给出3、5、17、257、65537，都是质数，由于F5太大（F5=4292967297），他没有再往下检测就直接猜测：对于一切自然数，Fn都是质数。但是，就是在F5上出了问题！费尔马死后67年，25岁的瑞士数学家欧拉证明：F5=4292967297=641*6700417，并非质数，而是合数。 更加有趣的是，以后的Fn值，数学家再也没有找到哪个Fn值是质数，全部都是合数。目前由于平方开得较大，因而能够证明的也很少。现在数学家们取得Fn的最大值为：n=1495。这可是个超级天文数字，其位数多达10^10584位，当然它尽管非常之大，但也不是个质数。质数和费尔马开了个大玩笑！ 17世纪还有位法国数学家叫梅森，他曾经做过一个猜想：2^p-1代数式，当p是质数时，2^p-1是质数。他验算出了：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2^p-1是质数。 p＝2，3，5，7时，Mp都是素数，但M11＝2047＝23×89不是素数。 还剩下p=67、127、257三个梅森数，由于太大，长期没有人去验证。梅森去世250年后，美国数学家科勒证明，2^67-1=193707721*761838257287，是一个合数。这是第九个梅森数。20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。质数排列得这样杂乱无章，也给人们寻找质数规律造成了困难。 还有一种质数叫费马数。形式是:Fn=2^(2^n)+1 是质数的猜想。 如F1=2^(2^1)+1=5 F2=2^(2^2)+1=17 F3=2^(2^3)+1=257 F4=2^(2^4)+1=65537 F5=2^(2^5)+1=4294967297 前4个是质数,因为第5个数实在太大了,费马认为是实数,并提出(费马没给出证明) 后来欧拉算出F5=641*6700417. 目前只有n=0,1,2,3,4,Fn才是质数. 现在，数学家找到的最大的梅森数是一个有9808357位的数：2^32582657-1。数学虽然可以找到很大的质数，但质数的规律还是无法循通。
编辑本段入门
最小的素数是2， 他也是唯一的偶素数。 最前面的素数依次排列为：2，3，5，7，11，13，17，...... 不是质数且大于1的正整数称为合数。 质数表上的质数请见素数表。 依据定义得公式： 设A=n2+b=(n-x)(n+y),除n-x=1以外无正整数。故有： y=（b+nx)/(n-x) (x1993，那么我们只要用1993去除<50的质数就可以了。100以内的质数有25个，还是比较好记的，我们只要记熟100以内质数，就可以快速判断10000以内的数是不是质数了。
编辑本段分布问题
素数分布问题，就是指素数在正整数集或其特殊子集中的分布情况，比如素数个数问题等等。这方面的结果如下; （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是一个素数”《代数学辞典》上海教育出版社1985年259页。参见百度素数普遍公式 可以用公式表示，参见下面筛法。
编辑本段各类猜想
上面我们已经提及了几类猜想， 如梅森素数无限的猜想， 费马素数有限的猜想等等。以下列举其他一些重要猜想。 （1）黎曼猜想。 黎曼通过研究发现， 素数分布的绝大部分猜想都取决于黎曼zeta函数ζ（s）的零点位置。他猜测那些非平凡零点都落在复平面中实部为1/2的直线上， 这就是被誉为千禧年世界七大数学难题之一的黎曼猜想， 是解析数论的重要课题。 （2）孪生素数猜想。 如果p和p+2都是素数， 那么就称他们为孪生素数。一个重要的问题就是：是否存在无限多对孪生素数？这一问题至今没有突破性进展。 （3）哥德巴赫猜想 （Goldbach Conjecture) （a）所有的不小于6的偶数，都可以表示为两个奇素数之和 (一般用代号“1+1”表示)。 （b）每个不小于9的奇数都可以表示为三个奇素数之和。 问题的第二部分，利用解析数论中的圆法估计，已被证明。 真正困难的是第一部分。
编辑本段哥德巴赫猜想
哥德巴赫猜想是德国数学家哥德巴赫（C．Goldbach，1690-1764）于1742年6月7日在给大数学家欧拉的信中提出的，所以被称作哥德巴赫猜想。同年6月30日，欧拉在回信中认为这个猜想可能是真的，但他无法证明。从此，这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。 18、19世纪，所有的数论专家对这个猜想的证明都没有作出实质性的推进，直到20世纪才有所突破。直接证明哥德巴赫猜想不行，人们采取了“迂回战术”，就是先考虑把偶数表为两数之和，而每一个数又是若干素数之积，被称为“殆素”意思是很像素数。如果把命题"每一个大偶数可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a＋b"，那么哥氏猜想就是要证明"1＋1"成立。 “充分大的偶数”陈景润是指10的5000000次方，即在10的后面加上500000个“0”。 哥德巴赫猜想至今没有任何实质性进展。 1920年，挪威的布朗证明了‘“9 + 9”。 1924年，德国的拉特马赫证明了“7 + 7”。 1932年，英国的埃斯特曼证明了“6 + 6”。 1937年，意大利的蕾西先后证明了“5 + 7”, “4 + 9”, “3 + 15”和“2 + 366”。 1938年，苏联的布赫夕太勃证明了“5 + 5”。 1940年，苏联的布赫夕太勃证明了“4 + 4”。 1948年，匈牙利的瑞尼证明了“1 + c”，其中c是一很大的自然数。 1956年，中国的王元证明了“3 + 4”。 1957年，中国的王元先后证明了 “3 + 3”和“2 + 3”。 1962年，中国的潘承洞和苏联的巴尔巴恩证明了“1 + 5”， 中国的王元证明了“1 + 4”。 1965年，苏联的布赫 夕太勃和小维诺格拉多夫，及 意大利的朋比利证明了“1 + 3 ”。 1966年，中国的陈景润证明了 “1 + 2 ”。
编辑本段英文解释
mathematics, a prime number (or prime) is a natural number greater than one whose only positive divisors are one and itself. Or for short: A prime number is a natural number with exactly two natural divisors. A natural number that is greater than one and is not a prime is called a composite number. The numbers zero and one are neither prime nor composite. The property of being a prime is called primality. Prime numbers are of fundamental importance in number theory. [From Wikipedia] 2.A whole number not divisible without a remainder by any whole number other than itself and one.（汉译：素数，质数：只能被其本身和一整除而没有余数的整数）[From American Heritage Dictionary] 3.any integer other than 0 or ± 1 that is not divisible without remainder by any other integers except ± 1 and ± the integer itself. [From The Merriam-Webster';s Collegiate® Dictionary] 4.a number that can be divided only by itself and the number one. For example, three and seven are prime numbers.[From Longman Dictionary of Contemporary English]
编辑本段筛法
筛法，是求不超过自然数N（N＞1）的所有质数的一种方法。据说是古希腊的埃（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛子。 具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。） 筛法与公式的关系： 素数普遍公式： 公元前250年同样是古希腊的数学家埃拉托塞尼提出一种筛法： （一）“要得到不大于某个自然数N的所有素数，只要在2---N中将不大于√N的素数的倍数全部划去即可”。 （二）将上面的内容等价转换：“如果N是合数，则它有一个因子d满足1 #include /* input: num, num should >0 return: 1 - 是质数 0 - it is NOT a prime number 不是质数 note: 只需要计算到num的平方根处。 */ int isprime( int num ) { int i ; int sq； if ( num <= 1) return 0; sq= ( int )sqrt( num ); for ( i = 2 ; i <= sq ; i++ ) { if ( num % i == 0 ) { break ; } } if ( i <= sq ) return 0; else return 1 ; } int main(void) { int pnPrimeList[100]={0}; int ntotal = 0; for(int i=0;i<=100;i++) { if(1==isprime(i)) { pnPrimeList[ntotal]=i; ntotal++; } } for(int j=0;j=2） public class PrimeNumber { public void sum(int max) { for (int i = 2; i <= max; i++) { int flag = 0; for (int j = 2; j < i; j++) { if (i % j == 0) { flag = 1; break; } } if (flag == 0) { System.out.print(" " + i + " "); } } } public static void main(String[] args) { PrimeNumber pn = new PrimeNumber(); pn.sum(100); } } |
IP卡
狗仔卡
发表于 2010-12-15 22:19
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡