『壹』 如何快速檢查一個素數的素性（演算法）
算好,我以前也研究過素數問題.現在資料還保存著.. 拿來給你分享吧. (這個演算法檢測速度,還是很快的,你可以試試看哦~~)
一種適合32位機器數的確定性素數判定法
作者：
王浩（[email protected]）
此論文是為發布個人研究成果與大家分享交流而提交，本人教育背景如下：
計算機應用專業/管理工程專業雙學士
天津大學
於1995年到1999年在校就讀
日期________________2006-11-28___________________
摘要
一種適合32位機器數的確定性素數判定法
作者：王浩
本文通過對米勒-拉賓非確定性素數判定法如何轉化為確定性素數判定法的研究，發現了與之相關的偽素數的一些性質，引入了偽素數的最小可判定底數的概念，並總結出了一些規律。通過這些規律找出了一種特別適合32位機器數的確定性素數判定法，該方法對於32位機器數進行素數判定最多隻需要進行16log(n) 次乘/除法。該方法具有實現簡單、速度快的優點，非常具有推廣價值。
本文中總結出的一些規律如果能夠得到證明和推廣，則有可能徹底解決把米勒-拉賓非確定性素數判定法轉化為確定性素數判定法的問題，從而對素數判定理論和實踐產生一定的促進作用。
本文共有五章。分述如下：
第一章：講述素數判定法的現狀，列舉了目前常用的一些素數判定法及其適用范圍。
第二章：講解偽素數表生成過程。
第三章：分析偽素數表，引入了偽素數的最小可判定底數的概念，並且總結出了一些規律。根據這些規律，找出了一種特別適合32位機器數的確定性素數判定法，並且進行了多種優化，給出了時間復雜度分析。
第四章：演算法的C++語言實現和解釋說明。
第五章：演算法的可推廣性分析和未來發展展望。
目錄
第一章 素數判定法現狀... 1
第二章 2-偽素數表的生成... 2
第三章 尋找2-偽素數的最小可判定底數... 3
第四章 演算法實現和解釋... 5
第五章 演算法可推廣性分析... 8
參考文獻... 9
詞彙表
素數判定法：判定一個自然數是否素數的方法。
確定性素數判定法：一個素數判定法判定某個自然數為素數的充要條件是該自然數確實是素數，該判定法就是確定性素數判定法。即該判定法不存在誤判的可能性。
32位機器數：在計算機上用32個二進制位表示的無符號整數。
64位機器數：在計算機上用64個二進制位表示的無符號整數。
第一章 素數判定法現狀
現在，確定性素數判定法已經有很多種，常用的有試除法、威廉斯方法、艾德利曼和魯梅利法。它們的適用范圍各不相同，威廉斯方法比較適合10^20到10^50之間的數，艾德利曼和魯梅利法適合大於10^50的數，對於32位機器數，由於都小於10^10，所以一般都用試除法來判定。
也許有人會問：「你為什麼沒有提馬寧德拉.阿格拉瓦法呢？不是有人說它是目前最快的素數判定法嗎？」 其實這是一個很大的誤解，阿格拉瓦法雖然是log(n)的多項式級演算法，但目前只有理論上的意義，根本無法實用，因為它的時間復雜度是O(log(n)^12)，這個多項式的次數太高了。就拿最慢的試除法跟它來比吧，試除法的時間復雜度為O(n^(1/2)*log(n)^2)，當n = 16時，log(n)^12 = 16777216，而n^(1/2)*log(n)^2 = 64，你看相差有多麼大！如果要讓兩者速度相當，即log(n)^12 = n^(1/2)*log(n)^2，得出n = 10^43.1214，此時需要進行的運算次數為log(n)^12 = 10^25.873（注意：本文中log（）函數預設以2為底），這樣的運算次數在一台主頻3GHz的計算機上運行也要10^8.89707年才能運行完，看來我們這輩子是別指望看到阿格拉瓦法比試除法快的這一天啦！
除了這些確定性素數判定法外，還有基於概率的非確定性素數判定法，最常用的就是米勒-拉賓法。
對於32位機器數（四則運算均為常數時間完成），試除法的時間復雜度是O(n^(1/2))，而米勒-拉賓法的時間復雜度只有O(log(n))。所以後者要比前者快得多，但是由於米勒-拉賓法的非確定性，往往我們在需要確定解時仍然要依靠速度較慢的試除法。那是否可以通過擴展米勒-拉賓法，來找到一種更快的確定性素數判定法呢？結論是肯定的，本文就帶你一起尋找這樣一種方法。
第二章 2-偽素數表的生成
既然要擴展米勒-拉賓法，那首先我們應該知道為什麼米勒-拉賓法是個非確定性素數判定法？答案很簡單，由於偽素數的存在。由於米勒-拉賓法使用費爾馬小定理的逆命題進行判斷，而該逆命題對極少數合數並不成立，從而產生誤判，這些使費爾馬小定理的逆命題不成立的合數就是偽素數。為了研究偽素數，我們首先需要生成偽素數表，原理很簡單，就是先用篩法得出一定范圍內的所有素數，然後逐一判定該范圍內所有合數是否使以2為底數的費爾馬小定理的逆命題不成立，從而得出該范圍內的2-偽素數表。我的程序運行了100分鍾，得出了32位機器數范圍內的2-偽素數表，如下：
341
561
645
1105
1387
1729
1905
2047
2465
2701
...
...
...
4286813749
4288664869
4289470021
4289641621
4289884201
4289906089
4293088801
4293329041
4294868509
4294901761
（共10403個，由於篇幅所限，中間部分省略。）
第三章 尋找2-偽素數的最小可判定底數
對於2-偽素數表的每一個偽素數，尋找最小的可以判定它們是合數的底數，我把這個底數稱之為最小可判定底數。特別地，對於絕對偽素數，它的最小質因子即是它的最小可判定底數。由於已經證明了絕對偽素數至少有三個質因子，所以這個最小質因子一定不大於n^(1/3)。下面就是我找到的最小可判定底數列表：
341 3
561 3
645 3
1105 5
1387 3
1729 7
1905 3
2047 3
2465 5
2701 5
...
...
...
4286813749 3
4288664869 3
4289470021 5
4289641621 3
4289884201 3
4289906089 3
4293088801 3
4293329041 3
4294868509 7
4294901761 3
通過統計這個列表，我發現了一個規律，那就是所有的最小可判定底數都不大於n^(1/3)，由前述可知，對於絕對偽素數，這個結論顯然成立。而對於非絕對偽素數，雖然直觀上覺得它應該比絕對偽素數好判定出來，但是我無法證明出它的最小可判定底數都不大於n^(1/3)。不過沒關系，這個問題就作為一個猜想留給數學家來解決吧，更重要的是我已經通過實驗證明了在32位機器數范圍內這個結論成立。
我們還有沒有更好的方法來進一步減小最小可判定底數的范圍呢？有的！我們可以在計算平方數時進行二次檢測，下面是進行了二次檢測後重新計算的最小可判定底數列表：
341 2
561 2
645 2
1105 2
1387 2
1729 2
1905 2
2047 3
2465 2
2701 2
...
...
...
4286813749 2
4288664869 2
4289470021 2
4289641621 2
4289884201 2
4289906089 2
4293088801 2
4293329041 2
4294868509 2
4294901761 3
很顯然，二次檢測是有效果的，經過統計，我發現了新的規律，那就是經過二次檢測後所有的最小可判定底數都不大於n^(1/6)，真的是開了一個平方呀，哈哈！這個結論的數學證明仍然作為一個猜想留給數學家們吧。我把這兩個猜想叫做費爾馬小定理可判定上界猜想。而我已經完成了對32位機器數范圍內的證明。
通過上面總結的規律，我們已經可以設計出一個對32位機器數進行素數判定的 O(n^(1/6)*log(n)) 的確定性方法。但是這還不夠，我們還可以優化，因為此時的最小可判定底數列表去重後只剩下了5個數（都是素數）：{2,3,5,7,11}。天哪，就是前5個素數，這也太容易記憶了吧。
不過在實現演算法時，需要注意這些結論都是在2-偽素數表基礎上得來的，也就是說不管如何對2的判定步驟必不可少，即使當2>n^(1/6)時。
還有一些優化可以使用，經過實驗，當n>=7^6時，可以不進行n^(1/6)上界限制，而固定地用{2,5,7,11}去判定，也是100%正確的。這樣就可以把判定次數降為4次以下，而每次判定只需要進行4log(n)次乘除法（把取余運算也看作除法），所以總的計算次數不會超過16log(n)。經過實驗，最大的計算次數在n=4294967291時出現，為496次。
第四章 演算法實現和解釋
演算法實現如下：（使用C++語言）
#include <iostream>
#include <math.h>
using namespace std;
//定義跨平台的64位機器數類型
#ifndef _WIN32
typedef unsigned long long longlong_t;
#else
typedef unsigned __int64 longlong_t;
#endif
//使用費爾馬小定理和二次檢測針對一個底數進行判定
bool IsLikePrime(longlong_t n, longlong_t base)
{
longlong_t power = n-1;
longlong_t result = 1;
longlong_t x = result;
longlong_t bits = 0;
longlong_t power1 = power;
//統計二進制位數
while (power1 > 0)
{
power1 >>= 1;
bits++;
}
//從高位到低位依次處理power的二進制位
while(bits > 0)
{
bits--;
result = (x*x)%n;
//二次檢測
if (result == 1 && x != 1 && x != n-1)
{
return false;
}
if ((power&((longlong_t)1<<bits)) != 0)
{
result = (result*base)%n;
}
x = result;
}
//費爾馬小定理逆命題判定
return result == 1;
}
//前5個素數
const int primes[]={2,3,5,7,11};
//前5個素數的6次方，由後面的init對象初始化
int primes_six[sizeof(primes)/sizeof(primes[0])];
//靜態初始化類
class CInit
{
public:
CInit()
{
int num = sizeof(primes)/sizeof(primes[0]);
for (int i = 0; i < num; i++)
{
primes_six[i] = primes[i]*primes[i]*primes[i];
primes_six[i] *= primes_six[i];
}
}
}init;
//王浩素數判定函數
bool JudgePrime(longlong_t n)
{
if (n < 2)
return false;
if (n == 2)
return true;
int num = sizeof(primes)/sizeof(int);
bool bIsLarge = (n >= primes_six[3]);
for (int i = 0; i < num; i++)
{
if (bIsLarge)
{
//當n >= 7^6時，不進行上界判斷，固定地用{2,5,7,11}做判定。
if (primes[i] == 3)
continue;
}
else
{
//當n < 7^6時，進行上界判斷，但是2例外。
if (primes[i] != 2 && n < primes_six[i])
break;
}
//做一次子判定
if (!IsLikePrime(n, primes[i]))
return false;
}
//所有子判定通過，則n必為素數！
return true;
}
//主程序
int main()
{
longlong_t n;
//對標准輸入的每一個數進行素數判定
while (cin >> n)
{
if (JudgePrime(n))
{
//如果是素數，則輸出到標准輸出。
cout << n << endl;
}
//如果是合數，不輸出。
}
return 0;
}
程序中已經加了足夠的注釋，應該不難理解。
需要說明的一點是，雖然我在輸入時使用了longlong_t，那是為了類型一致性，有效的輸入范圍仍然是0 ~ 2^32-1 。
第五章 演算法可推廣性分析
如果前述的費爾馬小定理可判定上界猜想可以被證明，那麼該演算法可以被推廣到任意位數的n，此時的時間復雜度為O(n^(1/6)*log(n)^3)。這樣我們就可以完成米勒-拉賓非確定性素數判定法向確定性素數判定法的轉化，這對於數論理論是一個補充，對於實踐中使用米勒-拉賓素數判定法具有指導意義。
本文所做的研究只是向米勒-拉賓非確定性素數判定法的確定化方向邁出了一小步，我相信，在不久的將來，米勒-拉賓非確定性素數判定法的確定化方向會有更大進展，從而對數論理論和實踐產生深遠影響。
參考文獻
《計算機演算法設計與分析（第2版）》，王曉東編著，電子工業出版社，2004年7月。
『貳』 小兒補液怎麼計算
中等脫水一般按100ml/kg計算，那麼是8kg×100＝800ml，等滲性脫水，那麼是0.9%鹽水400ml,5%糖水400ml,(10%糖水是高糖，一般不用、但用可以也是400)，這是一日量，先補400ml，再觀察，總的講缺多少補多少，補到小孩有尿為止，如果沒有尿，證明還有缺水的現象，補5%的蘇打水一般要看二氧化氮結合力來定，中等脫水一般用1—2ml/kg,計算，為安全起見，你給孩子補8ml、加入100ml糖水中滴。一般來講，只要小孩有尿，不需要補蘇打水，因為腎臟通過排尿自己能調節酸鹼平衡，
『叄』 快速排序演算法（free pascal)詳解，不要源程序，時間復雜度n（logn）；謝了//
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一不部分的所有數據都要小，然後再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然後將所有比它的數都放到它前面，所有比它大的數都放到它後面，這個過程稱為一躺快速排序。一躺快速排序的演算法是：
1）、設置兩個變數I、J，排序開始的時候I：=1，J：=N；
2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即由後開始向前搜索（J：=J-1），找到第一個小於X的值，兩者交換；
4）、從I開始向後搜索，即由前開始向後搜索（I：=I+1），找到第一個大於X的值，兩者交換；
5）、重復第3、4步，直到I>j；
詳細過程舉例如下：
原序： [26 5 37 1 61 11 59 15 48 19]
一： [19 5 15 1 11] 26 [59 61 48 37]
二： [11 5 15 1] 19 26 [59 61 48 37]
三： [1 5] 11 [15] 19 26 [59 61 48 37]
四： 1 5 11 [15] 19 26 [59 61 48 37]
五： 1 5 11 15 19 26 [59 61 48 37]
六： 1 5 11 15 19 26 [37 48] 59 [61]
七： 1 5 11 15 19 26 37 48 59 [61]
八： 1 5 11 15 19 26 37 48 59 61
快速排序法是所有排序方法中速度最快、效率最高的方法。程序如下：
var a:array[0..10] of integer；
n:integer;
procere qsort(l,r:longint);{r，l表示集合的左右邊界，即把第r到第l個數進行排序}
var i,j,m:longint;
begin
m:=a[l];{標准數}
i:=l; {I，J為指針}
j:=r;
repeat
while a[i]<m do inc(i);
while a[j]>m do dec(j);
if i<=j then begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j); {如果集合中不止一個數則進入下一層遞歸，l，J為新邊界}
if i<rthen qsort(i,r); {如果集合中不止一個數則進入下一層遞歸，i，r為新邊界}
end;
begin
for n:=1 to 10 do read(a[n]);
qsort(1,10);
for n:=1 to 10 do write(a[n]:4);
end.
『肆』 關於數學速演算法
較快的加減乘除的速算推薦珠心算。當然也取決教的老師和學習者的個人領悟能力。