来自当知百科
跳转到: 导航搜索

  最小的素数是2, 他也是唯一的偶素数。最前面的素数依次排列为:2,3,5,7,11,13,17,......

  不是质数且大于1的正整数称为合数。

  质数表上的质数请见素数表。

  依据定义得公式:

  设A=n2+b=(n-x)(n+y),除n-x=1以外无正整数。故有:

  y=(b+nx)/(n-x) (x<N-1)无正整数,则A为素数。

  因为x<N-1,而且N-X必为奇数,所以计算量比常规少很多。

  详见互动百科素数分布和不定方程

  100以内的质数(素数):2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97(共25个)

目录

算术基本定理

  算术基本定理:

  任何大于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。

  其中

  
4c3ebad7a2150.jpg
(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 numbergreater than one whose only positive divisors are one and itself.Or for short: A prime number is a natural number with exactly twonatural divisors. A natural number that is greater than one and isnot a prime is called a composite number. The numbers zero and oneare neither prime nor composite. The property of being a prime iscalled primality. Prime numbers are of fundamental importance innumber theory. [From Wikipedia]

  2.A whole number not divisible without a remainder by any wholenumber other than itself and one.(汉译:素数,质数:只能被其本身和一整除而没有余数的整数)[FromAmerican Heritage Dictionary]

  3.any integer other than 0 or ± 1 that is not divisible withoutremainder by any other integers except ± 1 and ± the integeritself. [From The Merriam-Webster's Collegiate&reg;Dictionary]

  4.a number that can be divided only by itself and the number one.For example, three and seven are prime numbers.[From LongmanDictionary 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<D≤√N”。(《基础数论》13页,U杜德利著,上海科技出版社)。.

  (三)再将(二)的内容等价转换:“若自然数N不能被不大于(根号)√N的任何素数整除,则N是一个素数”。见(代数学辞典[上海教育出版社]1985年。屉部贞世朗编。259页)。

  (四)这句话的汉字可以等价转换成为用英文字母表达的公式:

  N=p1m1+a1=p2m2+a2=......=pkmk+ak 。(1)

  其中p1,p2,.....,pk表示顺序素数2,3,5,,,,,。a≠0。即N不能是2m+0,3m+0,5m+0,...,pkm+0形。若N<P(k+1)的平方[注:后面的1,2,3,....,k,(k+1)是脚标,由于打印不出来,凡字母后面的数字或者i与k都是脚标],则N是一个素数。

  (五)可以把(1)等价转换成为用同余式组表示:

  N≡a1(modp1), N≡a2(modp2),.....,N≡ak(modpk)。 (2)

  例如,29,29不能够被根号29以下的任何素数2,3,5整除,29=2x14+1=3x9+2=5x5+4。29≡1(mod2),29≡2(mod3), 29≡4(mod5)。29小于7的平方49,所以29是一个素数。

  以后平方用“*”表示,即:㎡=m*。

  由于(2)的模p1,p2,....,pk两两互素,根据孙子定理(中国剩余定理)知,(2)在p1p2.....pk范围内有唯一解。

  例如k=1时,N=2m+1,解得N=3,5,7。求得了(3,3*)区间的全部素数。

  k=2时,N=2m+1=3m+1,解得N=7,13,19;N=2m+1=3m+2,解得N=5,11,17,23。求得了(5,5*)区间的全部素数。

  k=3时,

  ---------------------| 5m+1-|- 5m+2-| 5m+3,| 5m+4.|

  ---------------------|---------|----------|--------|---------|

  n=2m+1=3m+1= |--31----|--7, 37-|-13,43|--19----|

  n=2m+1=3m+2= |-11,41-|-17,47-|--23---|---29---|

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

  求得了(7,7*)区间的全部素数。

  仿此下去,可以求得任意大的数以内的全部素数。

  文章(作者王晓明)。

孪生素数普遍公式

  有定理:若自然数Q与Q+2不能被不大于根号(Q+2)的任何素数整除,则Q与Q+2是一对素数,称为孪生素数。这句话可以用公式表达:

  Q=p1m1+b1=p2m2+b2=.....=pkmk+bk 。(1)

   例如Q=41=2m+1=3m+2=5m+1。

  其中p1,p2,....,pk 表示顺序素数2,3,5,7,......。b≠0,和b≠pi-2。若Q〈P(K+1)的平方减2,[注:p后面的1,2,3,.....,k,k+1是脚标,凡是字母后面的

  数字和字母i,k 都是脚标] ,则Q与Q+2是一对孪生素数。

  即最小剩余不能是0和pi-2.,例如Q不能是2m,3m+1,5m+3,7m+5,....,pimi-2。否则Q+2是合数。

  (1)式可以用同余式组表示:

  Q≡b1(modp1),Q≡b2(modp2), .........,Q≡bk(modpk)。 (2)

  例如,41≡1(mod2),41≡2(mod3),41≡1(mod5)。41<41+2)的平方减2.,所以41与41+2是一对孪生素数。

  下面平方用“*”表示,即:㎡=m*.。

  由于(2)式的模p1,p2,....,pk两两互素,根据孙子定理(中国剩余定理)得知,对于给定的b值,(2)式在p1p2...pk范围内有唯一解。

  仅从(1)式看不出什么素数的规律,一旦转入同余式后,整个线路就清晰起来,因为在孙子定理的照耀下,我们知道b≠0,即是在p1p2p3...pk范围内筛去

  p1m+0,p2m+0,p3m+0,...,pkm+0形的数,筛k次。b≠pi-2即是从p1p2p3...pk范围内筛去p1m-2,p2m-2,p3m-2,...,pkm-2形的数,筛k次。共2k次。

  得知(1)(2)式在p1p2...pk范围内有:

  (2-1)×(3-2)×(5-2)×....×(pk-2) 。(3)

  个解。

C语言打印100以内的质数

  2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

  53 59 61 67 71 73 79 83 89 97

  #include<stdio.h>

  #include<math.h>

  /*

  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<ntotal;j++)

  {

  printf("%d ", pnPrimeList[j]);

  }

  printf("\ntotal number = %d\n",ntotal);

  return 0;

  }

JAVA质数升成

  n以内的质数(n>=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);

  }

  }

个人工具
名字空间

变换
查看
操作
导航
工具箱