小学学了的知识忘了:什么是素数

质数(又称为素数）

1就是在所有比1大的整数中，除了1和它本身以外，不再有别的因数，这种整数叫做质数。还可以说成质数只有1和它本身两个约数。2素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任 何其它两个整数的乘积。例如，15＝3＊5，所以15不是素数；

又如，12 ＝6＊2＝4＊3，所以12也不是素数。另一方面，13除了等于13＊1以 外，不能表示为其它任何两个整数的乘积，所以13是一个素数。

[编辑本段]质数的概念

一个数，如果只有1和它本身两个因数，这样的数叫做质数（或素数）。例如 2，3，5，7 是质数，而 4，6，8，9 则不是，后者称为合成数或合数。从这个观点可将整数分为两种，一种叫质数，一种叫合成数。（1不是质数，也不是合数）著名的高斯「唯一分解定理」说，任何一个整数。可以写成一串质数相乘的积。质数中除2是偶数外，其他都是奇数。

[编辑本段]质数的奥秘

质数的分布是没有规律的，往往让人莫名其妙。如：101、401、601、701都是质数，但上下面的301（743）和901（1753）却是合数。

有人做过这样的验算：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=4141。

说起质数就少不了哥德巴赫猜想，和著名的“1+1”

哥德巴赫猜想 ：(Goldbach Conjecture)

内容为“所有的不小于6的偶数，都可以表示为两个素数”

这个问题是德国数学家哥德巴赫（C．Goldbach，1690-1764）于1742年6月7日在给大数学家欧拉的信中提出的，所以被称作哥德巴赫猜想。同年6月30日，欧拉在回信中认为这个猜想可能是真的，但他无法证明。从此，这道数学难题引起了几乎所有数学家的注意。哥德巴赫猜想由此成为数学皇冠上一颗可望不可及的“明珠”。“用当代语言来叙述，哥德巴赫猜想有两个内容，第一部分叫做奇数的猜想，第二部分叫做偶数的猜想。奇数的猜想指出，任何一个大于等于7的奇数都是三个素数的和。偶数的猜想是说，大于等于4的偶数一定是两个素数的和。”（引自《哥德巴赫猜想与潘承洞》）

哥德巴赫猜想貌似简单，要证明它却着实不易，成为数学中一个著名的难题。18、19世纪，所有的数论专家对这个猜想的证明都没有作出实质性的推进，直到20世纪才有所突破。直接证明哥德巴赫猜想不行，人们采取了“迂回战术”，就是先考虑把偶数表为两数之和，而每一个数又是若干素数之积。如果把命题"每一个大偶数可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a＋b"，那么哥氏猜想就是要证明"1＋1"成立。

1900年，20世纪最伟大的数学家希尔伯特，在国际数学会议上把“哥德巴赫猜想”列为23个数学难题之一。此后，20世纪的数学家们在世界范围内“联手”进攻“哥德巴赫猜想”堡垒，终于取得了辉煌的成果。

到了20世纪20年代，有人开始向它靠近。1920年，挪威数学家布爵用一种古老的筛选法证明，得出了一个结论：每一个比6大的偶数都可以表示为（9+9）。这种缩小包围圈的办法很管用，科学家们于是从（9十9）开始，逐步减少每个数里所含质数因子的个数，直到最后使每个数里都是一个质数为止，这样就证明了“哥德巴赫猜想”。

1920年，挪威的布朗(Brun)证明了 “9+9 ”。

1924年，德国的拉特马赫(Rademacher)证明了“7+7 ”。

1932年，英国的埃斯特曼(Estermann)证明了 “6+6 ”。

1937年，意大利的蕾西(Ricei)先后证明了“5+7 ”, “4+9 ”, “3+15 ”和“2+366 ”。

1938年，苏联的布赫 夕太勃(Byxwrao)证明了“5+5 ”。

1940年，苏联的布赫 夕太勃(Byxwrao)证明了 “4+4 ”。

1948年，匈牙利的瑞尼(Renyi)证明了“1+c ”，其中c是一很大的自然数。

1956年，中国的王元证明了 “3+4 ”。

1957年，中国的王元先后证明了 “3+3 ”和 “2+3 ”。

1962年，中国的潘承洞和苏联的巴尔巴恩(BapoaH)证明了 “1+5 ”， 中国的王元证明了“1+4 ”。

1965年，苏联的布赫 夕太勃(Byxwrao)和小维诺格拉多夫(BHHopappB)，及 意大利的朋比利(Bombieri)证明了“1+3 ”。

1966年，中国的陈景润证明了 “1+2 ”[用通俗的话说，就是大偶数=素数+素数素数或大偶数=素数+素数（注：组成大偶数的素数不可能是偶素数，只能是奇素数。因为在素数中只有一个偶素数，那就是2。）]。

其中“s + t ”问题是指: s个质数的乘积 与t个质数的乘积之和

20世纪的数学家们研究哥德巴赫猜想所采用的主要方法，是筛法、圆法、密率法和三角和法等等高深的数学方法。解决这个猜想的思路，就像“缩小包围圈”一样，逐步逼近最后的结果。

由于陈景润的贡献，人类距离哥德巴赫猜想的最后结果“1＋1”仅有一步之遥了。但为了实现这最后的一步，也许还要历经一个漫长的探索过程。有许多数学家认为，要想证明“1＋1”，必须通过创造新的数学方法，以往的路很可能都是走不通的。实际上：

一陈景润证明的不是哥德巴赫猜想

陈景润与邵品宗合著的哥德巴赫猜想第118页（辽宁教育出版社）写道：陈景润定理的“1+1”结果，通俗地讲是指：对于任何一个大偶数N,那么总可以找到奇素数P',P",或者P1,P2,P3,使得下列两式至少一式成立：“

N=P'+P" (A)

N=P1+P2P3 (B)

当然并不排除(A)(B)同时成立的情形，例如62=43+19，62=7+5X11。”

众所周知，哥德巴赫猜想是指对于大于4的偶数（A)式成立，1+2是指对于大于10的偶数（B)式成立，

两者是不同的两个命题，陈景润把两个毫不相关的命题混为一谈，并在申报奖项时偷换了概念（命题），陈景润也没有证明1+2，因为1+2比1+1难得多。

二。 陈景润使用了错误的推理形式

陈采用的是相容选言推理的“肯定肯定式”：或者A，或者B，A，所以或者A或B，或A与B同时成立。 这是一种错误的推理形式，模棱两可，牵强附会，言之无物，什么也没有肯定，正如算命先生那样“：李大嫂分娩，或者生男孩，或者生女孩，或者同时生男又生女（多胎）”。无论如何都是对的，这种判断在认识论上称为不可证伪，而可证伪性是科学与伪科学的分界。相容选言推理只有一种正确形式。否定肯定式：或者A，或者B，非A，所以B。相容选言推理有两条规则：1，否认一部分选言肢，就必须肯定另一部分选言肢；2，肯定一部分选言肢却不能否定另一部份选言肢。可见对陈景润的认可表明中国数学会思维混乱，缺乏基本的逻辑训练。

三。 陈景润大量使用错误概念

陈在论文中大量使用“充分大”和“殆素数”这两个含糊不清的概念。而科学概念的特征就是：精确性，专义性，稳定性，系统性，可检验性。“殆素数”指很像素数，拿像与不像来论证，这是小孩的游戏。而“充分大”，陈指10的50万次方，这是不可检验的数。

四。陈景润的结论不能算定理

陈的结论采用的是特称（某些，一些），即某些N是(A)，某些N是（B)，就不能算定理，因为所有严格的科学的定理，定律都是以全称（所有，一切，全部，每个）命题形式表现出来，一个全称命题陈述一个给定类的所有元素之间的一种不变关系，适用于一种无穷大的类，它在任何时候都无区别的成立。而陈景润的结论，连概念都算不上。

五。陈景润的工作严重违背认识规律

在没有找到素数普篇公式之前，哥氏猜想是无法解决的，正如化圆为方取决于圆周率的超越性是否搞清，事物质的规定性决定量的规定性。（王晓明1999年《中华传奇》第三期“哥德巴赫猜想传奇）

英文的

prime number: a number that haas exact 2 foctor

[编辑本段]质数的性质

被称为“17世纪最伟大的法国数学家”费尔马，也研究过质数的性质。他发现，设Fn=2^(2^n)+1，则当n分别等于0、1、2、3、4时，Fn分别给出3、5、17、257、65537，都是质数，由于F5太大（F5=4294967297），他没有再往下检测就直接猜测：对于一切自然数，Fn都是质数。但是，就是在F5上出了问题！费尔马死后67年，25岁的瑞士数学家欧拉证明：F5=4294967297=6416700417，并非质数，而是合数。

更加有趣的是，以后的Fn值，数学家再也没有找到哪个Fn值是质数，全部都是合数。目前由于平方开得较大，因而能够证明的也很少。现在数学家们取得Fn的最大值为：n=1495。这可是个超级天文数字，其位数多达10^10584位，当然它尽管非常之大，但也不是个质数。质数和费尔马开了个大玩笑！

还有一种被称为“殆素数”的，意思是很像素数，著名数学家陈景润就使用了这个概念，他的“1+2”的“2”，就表示“殆素数”，实际上是一个合数。大家不要搞混了。严格地讲，“殆素数”不是一个科学概念，因为科学概念的特征是（1）精确性；（2）稳定性；（3）可以检验；（4）系统性；（5）专义性。例如，许多数学家使用了“充分大”，这也是一个模糊概念，因为陈景润把它定义为“10的50万次方”，即在10的后面加上50万个“0”。这是一个无法检验的数。

[编辑本段]质数的假设

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=193707721761838257287，是一个合数。这是第九个梅森数。20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。质数排列得这样杂乱无章，也给人们寻找质数规律造成了困难。

[编辑本段]质数表上的质数

现在，数学家找到的最大的梅森数是一个有9808357位的数：2^32582657-1。数学虽然可以找到很大的质数，但质数的规律还是无法循通。

30000以内的质数表

[编辑本段]求大质数的方法

研究发现质数除2以外都是奇数，而奇数除了奇数奇数(或再加“奇数”）都是质数。那么用计算机先把奇数奇数(或再加“奇数”）（比如9，15，21，25，27，33，35，39……）都求出来，再找奇数中上面没提到的那些数，那些数就是素数。

人们找出的几个超大质数中有遗漏，那么就可以用此方法求出那些遗漏的数，不过需要很长时间！

这对于“孪生素数”有帮助喔！

上面这个算法比较垃圾，对于求很大的素数效率低下，这个很大的素数可以用概率算法求。

求素数，请用《公理与素数计算》。这种方法用不着将所有奇数都写出来，而且计算出来的素数可以做到一个不漏。对于合数的删除，也不是涉及所有奇合数，删除是准确无误的，删除奇合数后剩余的全部是素数。如：对奇素数3的倍数的数进行删除，在整个自然数中只须删除一个数；对素数5的倍数的数进行删除，在整个自然数中只须删除2个数；对素数7的倍数的数进行删除，在整个自然数中只须删除8个数；以此类推，如果哪位老师能够将它用电脑编成程序，对计算素数有很大的帮助。

[编辑本段]质数的个数

有近似公式： x 以内质数个数约等于 x / ln(x)

ln是自然对数的意思。

尚准确的质数公式未给出。

10 以内共 4 个质数。

100 以内共 25 个质数。

1000 以内共 168 个质数。

10000 以内共 1229 个质数。

100000 以内共 9592 个质数。

1000000 以内共 78498 个质数。

10000000 以内共 664579 个质数。

100000000 以内共 5761455 个质数。

[编辑本段]求质数的方法

古老的筛法可快速求出100000000以内的所有素数。

筛法，是求不超过自然数N（N＞1）的所有质数的一种方法。据说是古希腊的埃拉托斯特尼（Eratosthenes，约公元前274～194年）发明的，又称埃拉托斯特尼筛子。

具体做法是：先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数。因为希腊人是把数写在涂腊的板上，每要划去一个数，就在上面记以小点，寻求质数的工作完毕后，这许多小点就像一个筛子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”，简称“筛法”。（另一种解释是当时的数写在纸草上，每要划去一个数，就把这个数挖去，寻求质数的工作完毕后，这许多小洞就像一个筛子。）

}

本机测试结果：10000000用时1156ms（1156秒）

100000000用时80秒（较慢，主要是内存太少，反复读硬盘的原因）

[编辑本段]判定质数的方法

1 朴素筛法，就是直接试除

2 若a是n的因子，那么n/a也是n的因子，所以如果n有一个大于1的真因子，则必有一个不大于n的1/2次方的因子

3 进一步的，如n是合数，他必有一个素因子不大于n的1/2次方，如要检测一个m以内的数是否为素数需事先建立一个m的1/2次方以内素数表。

4 Miller-Rabbin算法

5 概率算法

6 无条件的素数测试（包含APR算法 Jacobi sum测试 等）

7n的n次幂除以n，若余数为2，则n为质数

效率比较：

效率比较一般的有 Eraosthenes氏筛选法

效率较高的有

Jacobbi Sums测试

更好的有

Miller-Rabbin算法(Monte-Carlo系列的算法)

不过这个是概率算法,依赖于 ERH(extend Riemann Hypothesis)

现在使用的素数判定算法还有

Unconditional Primality Test(基于Algebraic Number Theory)

近15年来还有椭圆曲线算法，

APR, Random Curve, Abelian Variety测试

[编辑本段]素数的生成

根据素数定理，素数平均分布稠密程度π(x)/x≈1/lnx，对于512位大整数，随机产生为素数概率约为1/355，继而我们对每个随机数利用Miller-Rabbin测试，不断选取基b，计算是否每次都有bn-1 mod n=1都成立，则n几乎肯定是素数。由于多次运行后出错概率非常小，在实际中是可以信赖的。在Java里，BigInteger类提供的isProbablePrime()函数帮助简化了测试 *** 作。

代码仅供参考，属于概率型，不保证求出的都是质数。

素数是这样的整数，它除了能表示为它自己和1的乘积以外，不能表示为任何其它两个整数的乘积。例如，15＝3×5，所以15不是素数；又如，12＝6×2＝4×3，所以12也不是素数。另一方面，13除了等于13×1以外，不能表示为其它任何两个整数的乘积，所以13是一个素数。

有的数，如果单凭印象去捉摸，是无法确定它到底是不是素数的。有些数则可以马上说出它不是素数。一个数，不管它有多大，只要它的个位数是2、4、5、6、8或0，就不可能是素数。此外，一个数的各位数字之和要是可以被3整除的话，它也不可能是素数。但如果它的个位数是1、3、7或9，而且它的各位数字之和不能被3整除，那么，它就可能是素数（但也可能不是素数）。没有任何现成的公式可以告诉你一个数到底是不是素数。你只能试试看能不能将这个数表示为两个比它小的数的乘积。

找素数的一种方法是从2开始用“是则留下，不是则去掉”的方法把所有的数列出来（一直列到你不想再往下列为止，比方说，一直列到10，000）。

第一个数是2，它是一个素数，所以应当把它留下来，然后继续往下数，每隔一个数删去一个数，这样就能把所有能被2整除、因而不是素数的数都去掉。在留

下的最小的数当中，排在2后面的是3，这是第二个素数，因此应该把它留下，然后从它开始往后数，每隔两个数删去一个，这样就能把所有能被3整除的数全

都去掉。下一个未去掉的数是5，然后往后每隔4个数删去一个，以除去所有能被5整除的数。再下一个数是7，往后每隔6个数删去一个；再下一个数是11

，往后每隔10个数删一个；再下一个是13，往后每隔12个数删一个。……就这样依法做下去。

你也许会认为，照这样删下去，随着删去的数越来越多，最后将会出现这样的情况；某一个数后面的数会统统被删去崮此在某一个最大的素数后面，再也不

会有素数了。但是实际上，这样的情况是不会出现的。不管你取的数是多大，百万也好，万万也好，总还会有没有被删去的、比它大的素数。

事实上，早在公元前300年，希腊数学家欧几里得就已证明过，不论你取的数是多大，肯定还会有比它大的素数，假设你取出前6个素数，并把它们乘在

一起：2×3×5×7×11×13＝30030，然后再加上1，得30031。这个数不能被2、3、5、7、11、13整除，因为除的结果，每次都会余1。如果30031除了自己以外不能被任何数整除，它就是素数。如果能被其它数整除，那么30031所分解成的几个数，一定都大于13。事实上，3

0031＝59×509。

对于前一百个、前一亿个或前任意多个素数，都可以这样做。如果算出了它们的乘积后再加上1，那么，所得的数或者是一个素数，或者是比所列出的素数还要大的几个素数的乘积。不论所取的数有多大，总有比它大的素数，因此，素数的数目是无限的。

随着数的增大，我们会一次又一次地遇到两个都是素数的相邻奇数对，如5，7；11，13；17，19；29，31；41，43；等等。就数学家所能及的数来说，它们总是能找到这样的素数对。这样的素数对到底是不是有无限

个呢？谁也不知道。数学家认为是无限的，但他们从来没能证明它。这就是数学家为什么对素数感兴趣的原因。素数为数学家提供了一些看起来很容易、但事实

却非常难以解决的问题，他们目前还没能对付

加分加分

#include<stdioh>

#include <mathh>

int isprime(int n)

{

int i;

for(i=2;i<=(int)sqrt(n);i++)

if(n%i==0) return 0;

return 1;

}

void main()

{

int i,count;

for (i=2,count=0;count<=10;i++)

{

if(isprime(i) && isprime(i+2))

{printf("(%d,%d)\n",i,i+2);count++;}

}

}

//#include "stdafxh"//If the vc++60, with this line

#include <iostream>

using namespace std;

int prime(int n){//素数判断函数

int i;

for(i=3;ii<=n;i+=2)

if(!(n%i))

return 0;

return 1;

}

int main(int argc,char argv[]){

for(int n=3;n<98;n+=2)

if(prime(n) && prime(n+2))

cout << n << ' ' << n+2 << endl;

cout << endl;

return 0;

}

运行结果：

#include <stdioh>#include <mathh>int main(){ int m; / 输入的两个数据范围 / int i,j,k; int num=0, s; / 素数个数, 素数标志 / scanf( "%d", &m); for( i=m;i>=2;i-- ) { s = 1; / 先假设i是素数 / k = sqrt(i); for( j=2;j<=k;j++ ) { if( i%j == 0 ) { s = 0; / i不是素数 / break; } } if( s ) { k = sqrt( i+2 ); for( j=2;j<=k;j++ ) { if( (i+2)%j == 0 ) { s = 0; / i+2不是素数 / break; } } if( s ) { ++num; / i+2是素数 / printf( "第%d个孪生素数[%d,%d]\n", num, i, i+2 ); } }break; } return 0;}

#include <stdioh>

int prime(int n)

{int i;

for(i=2;i<n;i++)

if(n%i==0)

break;

if(i>=n&&i>1)

return 1;

else

return 0;

}

main()

{int i,a[200]={0},cnt=0;

for(i=2;i<200;i++)

if(prime(i))

a[cnt++]=i;

printf("孪生素数有以下数值:\n");

for(i=0;i<cnt;i++)

if(a[i]==a[i+1]-2)

printf("%4d<-->%-4d\n",a[i], a[i+1]);

}

另外，程序，只有正确程序和错误程序之分，没有什么标准答案，更不存在权威答案，得出结果就对了，顶多是执行效率和易读性的区别。

我这里虽然比大多数学生党风格多用了一个函数，但是减少了读程序的难度，把素数的判定单独拿到一个函数中，只需要调用这个函数就能确认某个数值是不是素数。

使用数组，虽然这段代码占用的内存空间比某些课本上要多百十倍，但电脑上并不缺这点内存，除非是单片机上跑程序，而且这样写下来，程序段落感更强更清晰。

思路：

1定义一个“函数prime”，判断该数是否是素数；

2主程序：

 1）输出（2,3）

 2）从3~999的所有奇数循环；

 3）如果这个数是素数，则判断这个数+2是不是素数，如果是，则输出（这个数，这个数+2）。

程序LZ可以自己试试看。

这个定义的函数prime的思路是：

1要判断一个数 n 是否是素数，可以从2~trunc(sqrt(n))循环，再看循环变量是否能整除 n ，如果都不能整除，则 n 是素数；

2过程如下：

function prime(n:longint):boolean;

var i:longint;

begin

prime:=true;

for i:=2 to trunc(sqrt(n)) do

if n mod i=0 then

begin

  prime:=false;

  exit;

end;

end;

这段代码不优化，不过由于是1000以内，还可以。

经过上机调试，测试通过，源代码见附件。

希望对你有帮助。

以上就是关于小学学了的知识忘了:什么是素数全部的内容，包括:小学学了的知识忘了:什么是素数、C语言编程序，打印前10对孪生素数。、用C++设计程序，求100以内的孪生素数对，要求用一个函数判断某一正整数是否为素数等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！