11213演算法

1. 10000以內的質數有什麼

10000以內的共1229個質數，如下圖所示：

質數又稱素數。一個大於1的自然數，除了1和它自身外，不能整除其他自然數的數叫做質數；否則稱為合數。

1、如果 為合數，因為任何一個合數都可以分解為幾個素數的積。

而N和N+1的最大公約數是1，所以不可能被p1，p2，……，pn整除，所以該合數分解得到的素因數肯定不在假設的素數集合中。因此無論該數是素數還是合數，都意味著在假設的有限個素數之外還存在著其他素數。所以原先的假設不成立。也就是說，素數有無窮多個。

2、其他數學家給出了一些不同的證明。歐拉利用黎曼函數證明了全部素數的倒數之和是發散的，恩斯特·庫默的證明更為簡潔，哈里·弗斯滕伯格則用拓撲學加以證明。

(1)11213演算法擴展閱讀：

質數的數目計算

盡管整個素數是無窮的，仍然有人會問「100，000以下有多少個素數？」，「一個隨機的100位數多大可能是素數？」。素數定理可以回答此問題。

1、在一個大於1的數a和它的2倍之間（即區間（a, 2a]中）必存在至少一個素數。

2、存在任意長度的素數等差數列。

3、一個偶數可以寫成兩個合數之和，其中每一個合數都最多隻有9個質因數。（挪威數學家布朗，1920年）

4、一個偶數必定可以寫成一個質數加上一個合成數，其中合數的因子個數有上界。（瑞尼，1948年）

5、一個偶數必定可以寫成一個質數加上一個最多由5個因子所組成的合成數。後來，有人簡稱這結果為 （1 + 5）（中國潘承洞，1968年）

6、一個充分大偶數必定可以寫成一個素數加上一個最多由2個質因子所組成的合成數。簡稱為 （1 + 2）

2. c++字元串演算法題（百度實習生2面題目） 1，2，3，4，5，6，7，8，9，10，11，12，13。。。

提問的時候把問題說清楚可以嗎？？？？

這道題是leetcode上的原題，用動態規劃很簡單就可以搞定

inttotalNum(string&s){
if(s.size()<=1){
return1;
}
vector<int>dp(s.size(),0);
dp[0]=1;
if(s[0]=='1'&&s[1]<='3'){
dp[1]=2;
}else{
dp[1]=1;
}
for(inti=2;i<s.size()-1;++i){
dp[i]+=dp[i-1];
if(s[i-1]=='1'&&s[i]<='3'){
dp[i]+=dp[i-2];
}
}
returndp[s.size()-1];
}

3. 如何求出當2的n次方減去1的值等於質數時的n值

2^n-1為素數時，成為梅森素數。以下是有關梅森素數的介紹。以及人們計算它的歷史。

十萬美元的懸賞——互聯網梅森素數大搜索

一、價值五萬美元的素數

2000年4月6日，住在美國密歇根州普利茅茨的那揚·哈吉拉特瓦
拉(Nayan Hajratwala)先生得到了一筆五萬美元的數學獎金，因為他
找到了迄今為止已知的最大素數，這是一個梅森素數：
2^6972593-1。
這也是我們知道的第一個位數超過一百萬位的素數。精確地講，如果
把這個素數寫成我們熟悉的十進制形式的話，它共有兩百零九萬八千
九百六十位數字，如果把它以這個形式寫下來，大約需要150到200篇
本文的篇幅。

可是哈吉拉特瓦拉先生並不是一個數學家，他甚至很可能對尋找
素數的數學理論一無所知——雖然這使他贏得了這筆獎金。他所做的
一切，就是從互聯網上下載了一個程序。這個程序在他不使用他的奔
騰II350型計算機時悄悄地運行。在經過111天的計算後，上面所說的
這個素數被發現了。

二、梅森素數

我們把一個大於1的自然數叫作素數，如果只有1和它本身可以整
除它。如果一個比1大的自然數不是素數，我們就叫它合數。1既不是
素數，也不是合數。

比如說，你很容易就可以驗證7是一個素數；而15是一個合數，因
為除了1和15外，3和5都可以整除15。根據定義，2是一個素數，它是
唯一的偶素數。早在公元前三百年的古希臘時代，偉大的數學家歐幾
里德就證明了存在著無窮多個素數。

關於素數，有許多既簡單又美麗，但是極為困難的，到現在還沒
有答案的問題。其中有著名的哥德巴赫猜想，它是說任何一個大於6的
偶數，都能表示為兩個奇素數之和。還有孿生素數問題。象5和7，41
和43這樣相差2的素數對，被稱為孿生素數。孿生素數問題是說：是不
是有無窮多對孿生素數？這里要順便提一下的是，這些看起來很簡單
的數學問題，它們的解決方法將一定是極其復雜的，需要最先進的數
學工具。如果你不是狂妄到認為幾百甚至幾千年來所有在這些問題上
耗費了無數聰明才智的數學家（有許多是非常偉大的）和數學愛好者
加起來都不如你聰明，就不要試圖用初等方法去解決這些問題，徒費
時間和精力。

古希臘人還對另一種數感興趣。他們將它稱為完美數。一個大於1
的自然數叫完美數，如果它的所有因子（包括1，但不包括本身）之和
等於它本身。比如說6=1+2+3就是最小的完美數，古希臘人把它看作維
納斯也就是愛情的象徵。28=1+2+4+7+14是另一個完美數。歐幾里德證
明了：一個偶數是完美數，當且僅當它具有如下形式：
2^(p-1)(2^p-1)
其中2^p-1是素數。上面的6和28對應著p=2和3的情況。我們只要找到
了一個形如2^p-1的素數，也就知道了一個偶完美數；我們只要找到所
有形如2^p-1的素數，也就找到了所有偶完美數。所以哈吉拉特瓦拉先
生不但找到了世界上已知的最大的素數，還找到了世界上已知的最大
的偶完美數。嗯，你要問，關於奇完美數又是怎麼樣的情況？回答是：
我們現在連一個奇完美數也沒有找到過，我們甚至根本不知道是不是
有奇完美數存在。我們只知道，要是有奇完美數存在的話，它一定是
非常非常大的！奇完美數是否存在這個問題，也是一個上面所說的既
簡單又美麗，但是極為困難的著名數學問題。

有很長一段時間人們以為對於所有素數p，
M_p=2^p-1
都是素數（注意到要使2^p-1是一個素數，p本身必須是一個素數，想
一想為什麼？）但是在1536年雷吉烏斯(Hudalricus Regius)指出，
M_11=2^11-1=2047=23*89不是素數。

皮特羅·卡達迪(Pietro Cataldi)首先對這類數進行了系統的
研究。他在1603年宣布的結果中說，對於p=17，19，23，29，31和37，
2^p-1是素數。但是1640年費爾馬使用著名的費爾馬小定理（不要和那
個費爾馬大定理混淆起來）證明了卡達迪關於p=23和37的結果是錯
誤的，歐拉在1738年證明了p=29的結果也是錯的，過後他又證明了關
於p=31的結論是正確的。值得指出的是，卡達迪是用手工一個一個
驗算取得他的結論的；而費爾馬和歐拉則是使用了在他們那時最先進
的數學知識，避免了許多復雜的計算和因此可能造成的錯誤。

法國神父梅森(Marin Mersenne)在1644年他發表了他的成果。他
宣稱對於p=2，3，5，7，13，17，19，31，67，127和257，2^p-1都是
素數，而對於其它小於257的素數p，2^p-1都是合數。今天我們把形如
M_p=2^p-1的素數叫做梅森素數，M_p中的M就是梅森姓氏的第一個字母。

用手工來判斷一個很大的數是否素數是相當困難的，梅森神父自
己也承認他的計算並不一定準確。一直要等到一個世紀以後，在1750
年，歐拉宣布說找到了梅森神父的錯誤：M_41和M_47也是素數。可是
偉大如歐拉也會犯計算錯誤——事實上M_41和M_47都不是素數。不過
這可不是說梅森神父的結果就是對的。要等到1883年，也就是梅森神
父的結果宣布了兩百多年後，第一個錯誤才被發現：M_61是一個素數。
然後其它四個錯誤也被找了出來：M_67和M_257不是素數，而M_89和
M_107是素數。直到1947年，對於p<=257的梅森素數M_p的正確結果才
被確定，也就是當p=2，3，5，7，13，17，19，31，61，89，107和
127時，M_p是素數。現在這個表已經被反復驗證，一定不會有錯誤了。

下面是我們現在知道的所有梅森素數的列表：（我們注意到梅森
神父的名字不在上面——這種素數已經由他的名字命名了，就把榮譽
分給最後確認者吧。）

序號 p M_p的位數 相對應的 確認 確認人
完美數的 年代
位數
1 2 1 1 ---- ----
2 3 1 2 ---- ----
3 5 2 3 ---- ----
4 7 3 4 ---- ----
5 13 4 8 1456 佚名
6 17 6 10 1588 Cataldi
7 19 6 12 1588 Cataldi
8 31 10 19 1772 Euler
9 61 19 37 1883 Pervushin
10 89 27 54 1911 Powers
11 107 33 65 1914 Powers
12 127 39 77 1876 Lucas
13 521 157 314 1952 Robinson
14 607 183 366 1952 Robinson
15 1279 386 770 1952 Robinson
16 2203 664 1327 1952 Robinson
17 2281 687 1373 1952 Robinson
18 3217 969 1937 1957 Riesel
19 4253 1281 2561 1961 Hurwitz
20 4423 1332 2663 1961 Hurwitz
21 9689 2917 5834 1963 Gillies
22 9941 2993 5985 1963 Gillies
23 11213 3376 6751 1963 Gillies
24 19937 6002 12003 1971 Tuckerman
25 21701 6533 13066 1978 Noll & Nickel
26 23209 6987 13973 1979 Noll
27 44497 13395 26790 1979 Nelson & Slowinski
28 86243 25962 51924 1982 Slowinski
29 110503 33265 66530 1988 Colquitt & Welsh
30 132049 39751 79502 1983 Slowinski
31 216091 65050 130100 1985 Slowinski
32 756839 227832 455663 1992 Slowinski & Gage
33 859433 258716 517430 1994 Slowinski & Gage
34 1257787 378632 757263 1996 Slowinski & Gage
35 1398269 420921 841842 1996 GIMPS
36 2976221 895932 1791864 1997 GIMPS
37 3021377 909526 1819050 1998 GIMPS
38 6972593 2098960 4197919 1999 GIMPS
39 13466917 4053947
40 20996011 6320431
41 24036583 7235734
42 25964951 7816230 2005

是不是有無窮多個梅森素數呢？數學家們目前還無法回答這個問
題。

三、尋找更大的素數

為什麼要尋找梅森素數？為什麼要打破已知最大素數的紀錄？這
有什麼用處呢？

如果你所說的用處是指能夠直接創造物質財富，那麼我不得不告
訴你——梅森素數沒有什麼用處，多知道一個非常大的素數似乎也沒
什麼用處。即使我們知道了一個無比巨大的梅森素數，也不會使我們
的錢包增加一分錢（嗨等一等！如果你只對錢感興趣的話，也請不要
立刻撇下我的文章。我其實是說，我上面說的話要排除我在這篇文章
題目中提到的那十萬美元的獎金——你的錢包也許會因此鼓起來的。
所以請耐心一點）。

但是人類並不只需要物質財富。博物館里的鑽石有什麼用場呢？
為什麼人類要收集它們？因為它們美麗而稀少。作為人類智慧的結晶，
素數、梅森素數和與它密切相關的完美數是非常美麗的。它們的定義
簡單，卻又如此神秘莫測，象歐幾里德、笛卡爾、費爾馬、萊布尼茲、
歐拉這樣的偉大數學家都因為它們的美麗而對它作過大量研究；大家
也看到，兩千多年來，經過無數代人的辛勤工作，我們一共只收集到
38個梅森素數，它們是非常稀少的。對於數學家來說，搜集素數、梅
森素數和完美數是和收集鑽石一樣富有樂趣的事情。

人類還需要榮耀——也許更勝於財富。在體育運動中，能夠跑得
更快一點，跳得更高一點，難道真的有實際物質方面的用途嗎？不，
我們喜歡接受挑戰，我們希望能贏。打破一個體育世界記錄，攀登珠
穆朗瑪峰，單身駕船橫穿太平洋……，那是對人類體能極限的挑戰；而尋
找更大的素數，則是一項對人類智慧的挑戰。當我們完成了一項前所
未有的任務時，我們總會感到無比驕傲。1963年，當第23個梅森素數
被找到時，發現它的美國伊利諾斯大學數學系是如此地驕傲，以致於
把所有從系裡發出的信件都敲上了「2^11213-1是個素數」的郵戳。

在歐拉證明M_31是素數以後，下一個最大素數的記錄由蘭德里
(Landry)於1867年獲得：M_59/179951=3203431780337。這不是一個梅
森素數。這個記錄保持了九年。

1876年愛德華·盧卡斯使用了一個比費爾馬和歐拉的方法更先進
的手段，證明了M_127是一個素數。這個記錄保持了七十五年。直到費
里葉(Ferrier)於1951年使用一部手搖計算機證明了(2^148+1)/17是一
個素數，它有41位數。

藉助手搖計算機的方法要算作手工計算方法還是要算做計算機方
法，大概是可以探討的問題。不過技術的發展一下子把這種爭論變得
毫無必要。值得指出的是，在人類尋找大素數的旅途中，數學理論的
改善要遠遠比具有強大堅韌的計算能力重要得多。盧卡斯的方法在
1930年被勒梅(Lehmer)簡化後，盧卡斯-勒梅測試成為現在尋找梅森素
數的標准方法。

（盧卡斯-勒梅測試：對於所有大於1的奇數p，M_p是素數當且僅當M_p
整除S(p-1)，其中S(n)由S(n+1)=S(n)^2-2，S(1)=4遞歸定義。
4 14 194 37634 1416317954 2005956546822746114
這個測
試尤其適合於計算機運算，因為除以M_p=2^p-1的運算在二進制下可以
簡單地用計算機特別擅長的移位和加法操作來實現。判斷一個梅森數
是素數的方法比判斷一個差不多大小的其他類型數是素數的方法要簡
單得多，所以在尋找最大素數的過程中，大部分紀錄都是梅森素數。）

在1951年米勒和維勒(Miller & Wheeler)藉助於EDSAC計算機（這
種計算機還不如我們現在使用的一般計算器，它只有5K的內存）發現
了長達79位的素數180(M_127)^2+1。這個記錄還是沒能保持多久。次
年羅賓遜應用SWAC計算機，在1952年初發現了第13和第14號梅森素數：
M_521和M_607，後面連續三個梅森素數也在同一年被陸續發現：M_1279，
M_2203和M_2281。

在那以後的年代裡，為了打破巨大素數紀錄而使用的計算機越來
越強大，其中有著名的IBM360型計算機，和超級計算機Cray系列。大
家可以參看上面的梅森素數表來了解這個競賽過程。在此其間只有一
次一個不是梅森素數的素數坐上過「已知最大素數」的寶座，它是
39158*2^216193-1，在1989年被發現。1996年發現的M_1257787是迄今
為止最後一個由超級計算機發現的梅森素數，數學家使用了Cray T94。

然後，GIMPS的時代到來了。

四、GIMPS——互聯網梅森素數大搜索

1995年程序設計師喬治·沃特曼(George Woltman)開始收集整理
有關梅森素數計算的數據。他編制了一個梅森素數尋找程序並把它放
在網頁上供數學愛好者免費使用。這就是「互聯網梅森素數大搜索」
計劃(GIMPS，the Great Internet Mersenne Prime Search)。在這個
計劃中，十幾位數學專家和幾千名數學愛好者正在尋找下一個最大的
梅森素數，並且檢查以前梅森素數紀錄之間未被探索的空隙。比如上
面的梅森素數表中，最後那個素數的序號是未知的，我們不知道第37
號梅森素數和它之間是否還存在著其他未被發現的梅森素數。

1997年斯科特·庫爾沃斯基(Scott Kurowski)和其他人建立了「素數
網」(PrimeNet)，使分配搜索區間和向GIMPS發送報告自動化。現在只
要你去GIMPS的主頁下載那個免費程序，你就可以立刻參加GIMPS計劃
搜尋梅森素數。幾乎所有的常用計算機平台都有可用的版本。程序以
最低的優先度在你的計算機上運行，所以對你平時正常地使用計算機
幾乎沒有影響。程序也可以隨時被停止，下一次啟動時它將從停止的
地方繼續進行計算。

從1996年到1998年，GIMPS計劃發現了三個梅森素數：M_1398269、
M_2976221和M_3021377，都是使用奔騰型計算機得到的結果。

1999年3月，在互聯網上活動的一個協會「電子邊界基金」(EFF，
Electronic Frontier Foundation)宣布了由一位匿名者資助的為尋找
巨大素數而設立的獎金。它規定向第一個找到超過一百萬位的素數的
個人或機構頒發五萬美元的獎金，這就是我們最一開始說到的哈吉拉
特瓦拉得到的獎金。後面的獎金依次為：超過一千萬位，十萬美元；
超過一億位，十五萬美元；超過十億位，二十五萬美元。

搜尋結果的驗證和獎金的頒發是非常嚴格的。比如說，得到的結
果必須是顯式的——你不能宣稱你的結果是一個有一百個方程組成的
方程組的解，卻不把它解出來。結果必須由另一台計算機獨立驗證。
所有這些規則都在EFF網站上進行了解釋。

應該指出的是，通過參加GIMPS計劃來獲得獎金的希望是相當小的。
哈吉拉特瓦拉使用的計算機是當時21000台計算機中的一台。每一個參
與者都在驗證分配給他的不同梅森數，當然其中絕大多數都不是素數
——他只有大約三萬分之一的可能性碰到一個素數。

下一個十萬美元的獎金將被頒發給第一個找到超過一千萬位的素
數的個人或機構。這一次的計算量將大約相當於上一次的125倍。現在
GIMPS得到的計算能力為每秒7000億次浮點運算，和一台當今最先進的
超級矢量計算機，比如Cray T932的運行能力相當。但是如果GIMPS要
使用這樣的超級計算機，一天就需要支付大約二十萬美元。而現在他
們需要的費用，僅僅是支持網站運行的費用，和總共幾十萬美元的
獎金罷了。

五、網上分布式計算計劃

GIMPS只不過是互聯網上眾多的分布式計算計劃中的一個，
GIMPS主頁上就有這些計劃的介紹。

分布式計算是一門計算機學科，它研究如何把一個需要非常巨大
的計算能力才能解決的問題分成許多小的部分，然後把這些部分分配
給許多計算機進行處理，最後把這些計算結果綜合起來得到最終的結
果。有時侯計算量是如此之大，需要全世界成千上萬甚至更多台計算
機一起工作，才能在合乎情理的時間內得到結果。GIMPS計劃就是在進
行這樣的分布式計算。

但它並不是最著名的分布式計算計劃。致力於尋找宇宙中智慧生
命的「搜尋地外文明計劃」(SETI計劃)中的SETI@HOME工程，已在全世
界招募了290萬名(!)志願者，利用屏幕保護程序來處理射電望遠鏡接
受到的大量的宇宙間傳來的無線電信號。如果你參加這個計劃，也許
有一天會在你的計算機上破譯出外星人發來的問候呢。

你也可以用你的計算機空餘的計算能力為人類征服癌症作出貢獻。
英國科學家設計了類似SETI@HOME工程的分布式計算屏保，它從有關網
站下載數據，分析化學物質分子的抗癌性能，然後將分析結果通過互
聯網傳回給研究人員，作為研製新型抗癌葯物的參考。這項工程將於
2001年4月3日在美國加利福尼亞州正式啟動。

計算機硬體的更新令人目不暇接，上半年買的最新式的個人電腦，
在下半年就變成了大路貨。三四年前的CPU，現在變得一錢不值——
也許不能這么說，你根本就買不到它們了——市面上最便宜的CPU也
要比它們強大得多。而一台普通的家用計算機連續運轉五年也是沒有
問題的。所以，對待計算機的最經濟的態度就是：讓它運轉。

而人類還有那麼多的東西需要計算，還有那麼多的問題需要找到
回答，還有那麼多的難關需要克服。我們需要越來越巨大的計算能力，
我們也擁有這樣的計算能力，只是太多太多被白白地閑置浪費掉了。
互聯網已經使大規模的分布式計算計劃成為可能。現在，我們唯一需
要的，就是這個網每一個結點上計算機用戶的意願和信心了。

4. C語言編程求素數的個數，計算1到1000000000(10億)以內的素數個數，有多少個附上程序

不知道有沒有國際最優，但我這個演算法很頂尖了：計算1億以內的素數個數不到2秒鍾！1到10000000000（10億）共有素數50847534個，計算時間大概20多秒！程序如下：#include<iostream>
using namespace std;
int main()
{int CompositeNumFilterV3(int);
int m,c;
cin>>m;
c=CompositeNumFilterV3(m);
cout<<c<<endl;
return 0;
}//求素數的程序
int CompositeNumFilterV3(int n)
{
int i, j;
//素數數量統計
int count = 0;
// 分配素數標記空間，明白+1原因了吧，因為浪費了一個flag[0]
char* flag = (char*)malloc( n+1 );
// 幹嘛用的，請仔細研究下文
int mpLen = 2*3*5*7*11*13;
char magicPattern[2*3*5*7*11*13]; // 奇怪的代碼，why，思考無法代勞，想！
for (i=0; i<mpLen; i++)
{
magicPattern[i++] = 1;
magicPattern[i++] = 0;
magicPattern[i++] = 0;
magicPattern[i++] = 0;
magicPattern[i++] = 1;
magicPattern[i] = 0;
}
for (i=4; i<=mpLen; i+=5)
magicPattern[i] = 0;
for (i=6; i<=mpLen; i+=7)
magicPattern[i] = 0;
for (i=10; i<=mpLen; i+=11)
magicPattern[i] = 0;
for (i=12; i<=mpLen; i+=13)
magicPattern[i] = 0; // 新的初始化方法,將2,3,5,7,11,13的倍數全乾掉
// 而且採用memcpy以mpLen長的magicPattern來批量處理
int remainder = n%mpLen;
char* p = flag+1;
char* pstop = p+n-remainder;
while (p < pstop)
{
memcpy(p, magicPattern, mpLen);
p += mpLen;
}
if (remainder > 0)
{
memcpy(p, magicPattern, remainder);
}
flag[2] = 1;
flag[3] = 1;
flag[5] = 1;
flag[7] = 1;
flag[11] = 1;
flag[13] = 1; // 從17開始filter，因為2,3,5,7,11,13的倍數早被kill了
// 到n/13止的，哈哈，少了好多吧
int stop = n/13;
for (i=17; i <= stop; i++)
{
// i是合數，請歇著吧，因為您的工作早有您的質因子代勞了
if (0 == flag[i]) continue;
// 從i的17倍開始過濾
int step = i*2;
for (j=i*17; j <= n; j+=step)
{
flag[j] = 0;
}
}

// 統計素數個數
for (i=2; i<=n; i++)
{
if (flag[i]) count++;
}

// 因輸出費時，且和演算法核心相關不大，故略
// 釋放內存，別忘了傳說中的內存泄漏
free(flag);

return count;
}