判斷質數演算法

㈠ 判斷一個數是不是質數的演算法,流程圖

是不是偶數（除了2以外的偶數都不是質數）——各位數之和是不是3的倍數（和是3的倍數的數不是質數）——末位數是不是0或5（末位數是0或5的數不是質數）——把它開方，拿小於開方數的質數（先）/奇數（後）從小到大試除，能被整除的不是質數

㈡ 請寫出判斷n(n＞2)是否為質數的演算法.

演算法如下： 第一步，給定大於2的整數n. 第二步，令i=2. 第三步，用i除n,得到余數r. 第四步，判斷「r=0」是否成立.若是，則n不是質數，結束演算法；否則，將i的值增加1，仍用i表示. 第五步，判斷「i＞（n-1）」是否成立.若是，則n是質數，結束演算法；否則，返回第三步. 分析：對於任意的整數n(n＞2)，若用i表示2—(n-1)中的任意整數，則「判斷n是否為質數」的演算法包含下面的重復操作：用i除n,得到余數r.判斷余數r是否為0，若是，則不是質數；否則，將i的值增加1，再執行同樣的操作. 這個操作一直要進行到i的值等於(n-1)為止.

㈢ 「判斷n是否為質數」的演算法

這里的i>(n-1)如果是成立，則說明在2-（n-1）之間沒有可以整除n的，也就說明n是質數，而如果不是，則i還未到n-1，不知道在i到n-1之間會不會有可以整除n的數，因此要返回步驟3繼續判斷i+1。如果還不理解可以追問。

㈣ 設計一個演算法判斷一個數是不是質數

演算法分析：（1）根據質數的定義，可以這樣判斷：依次用2—6除7，如果它們中有一個能整除7，則7不是質數，否則7是質數.
演算法如下：（1）第一步，用2除7，得到余數1.因為余數不為0，所以2不能整除7.
第二步，用3除7，得到余數1.因為余數不為0，所以3不能整除7.
第三步，用4除7，得到余數3.因為余數不為0，所以4不能整除7.
第四步，用5除7，得到余數2.因為余數不為0，所以5不能整除7.
第五步，用6除7，得到余數1.因為余數不為0，所以6不能整除7.因此，7是質數.
（2）類似地，可寫出「判斷35是否為質數」的演算法：第一步，用2除35，得到余數1.因為余數不為0，所以2不能整除35.
第二步，用3除35，得到余數2.因為余數不為0，所以3不能整除35.
第三步，用4除35，得到余數3.因為余數不為0，所以4不能整除35.
第四步，用5除35，得到余數0.因為余數為0，所以5能整除35.因此，35不是質數.
點評：上述演算法有很大的局限性，用上述演算法判斷35是否為質數還可以，如果判斷1997是否為質數就麻煩了，因此，我們需要尋找普適性的演算法步驟.

㈤ c語言如何判斷素數

素數又稱質數，所謂素數是指除了 1 和它本身以外，不能被任何整數整除的數，例如17就是素數，因為它不能被 2~16 的任一整數整除。判斷一個整數m是否是素數，只需把 m 被 2 ~ m-1 之間的每一個整數去除，如果都不能被整除，那麼 m 就是一個素數。

首先要知道素數是不等於1，它的因子只有1和它本身。判斷一個數是否為素數，可以用大於1小於給定數的所有數去除給定數，如果有任何一個能夠除盡，就表示是合數，反之是素數。

(5)判斷質數演算法擴展閱讀：

首先，本文英文字母都表示整數，上半部B 》3N 》W，下半部B 》W 》3N。大於3的素數只有6N-1和6N+1兩種形式，我們只需判定這兩種數是素數還是合數即可。

命題 1 對於B=36N+1 形數而言。

若不定方程（3N）^2+N-（B-1）/36=W^2 有整數解，

則 6（3N-W）+1 是小因子數；6（3N+W）+1 是大因子數。

若不定方程 （3N）^2-N-（B-1）/36=W^2 有整數解，

則 6（3N-W）-1 是小因子數；6（3N+W）-1 是大因子數。

兩式都無解，是素數。

㈥ 判斷一個數是否為素數的演算法

找質數的方法：寫出這個數的因數。再判斷這個數是質數還是合數。
1、一個數除了1和本身，不再有別的約數，這樣的數叫做質數或者素數。例如：2，3，5，7，11，13，17，19，23，29等等。
2、一個數，除了1和本身，還的別的因數，這樣的數叫做合數。例如4、8、8、9等等。例如：2的所有因數是1和2兩個，所以2是質數。例如6的所有因數是：1，2，3，6。一共是4個，所以6是合數。
找因12的因數：
1×12=12
2×6=12
3×4=12
所以12的因數有：1，2，3，4，6，12。共6個。
找因數的方法可以把這個數分成兩個因數相乘的積。從一開始比較容易找，寫的時候最好能從小到大寫出來。重復的只能寫一個。例如9的因數：1×9=9
3×3=9
9的因數是：1，3，9共3個。（重復的3隻能寫一個。）

㈦ 判斷是否為質數的快速演算法

#include<stdio.h>
#include<stdlib.h>
#define SIZE 1000000
char table[SIZE];
int prime[168]=
{
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,101,103,107,109,113,
127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,
199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,
283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,
383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,
467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,
577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,
661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,
769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,
877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,
983,991,997
};
int init()
{
int i,j;
memset(table,1,SIZE);
table[0]=table[1]=0;
for(i=0;i<168;++i)
{
for(j=prime[i]*2;j<SIZE;j+=prime[i])
{
table[j]=0;
}
}
}
int main()
{
int i;
init();
while(scanf("%d",&i)!=EOF)
{
printf(table[i]?"yes":"no");
}
return 0;
}

㈧ 質數的判別方法

數論中一個最基本、最古老而當前仍然受到人們重規的問題就是判別給定的整數是否素數(簡稱為素數判別或素性判別)和將大合數分解成素因子乘積(簡稱為大數分解)。在歷史上，這個問題曾經吸引了包括費馬(Fermat)、歐拉(Euler)、勒讓德(Legendre)和高斯(Gauss)在內的大批數學家，他們花費了大量的時間和精力去研究這個問題。高斯在其著名的《算術探討》(《Disquisitiones Arithmeticae》)中稱道：「把素數同合數鑒別開來及將合數分解成素因子乘積被認作為算術中最重要最有用的問題之一。」我國的《易經》中也對這個問題作了研究。
素數判別和大數分解這個問題具有很大的理論價值。因為素數在數論中佔有特殊的地位，鑒別它們則成為最基本的問題；而把合數分解成素因子的乘積是算術基本定理的構造性方面的需要。人類總是有興趣問如下的問題：2131-1是否素數？由23個1組成的數是否素數？怎麼分解31487694841572361？對素數判別和大數分解的研究必然會豐富人類的精神財富。更重要的是，素數判別和大數分解具有很大的應用價值。在編碼中，需要討論某類有限域及其上的多項式，這類有限域就是由素數
在快速數論變換中，要討論Z/nZ上的卷積運算，就要知道Z/nZ的乘法群的構造，而這就依賴於將n分解成素因子的乘積。下面介紹的RSA公開密鑰碼體制更加說明了這個問題的兩個方面在實際應用中的作用。1977年，艾德利曼(Adleman)、希愛默(Shamir)和魯梅利(Rumely)發明了一個公開密鑰碼體制。在這個密碼體制中，對電文的加密過程是公開的，但是，你僅知道加密過程而未被告知解密過程則不可能對電文進行解密。他們的體制就是依靠這樣一個事實：我們能夠很容易地將兩個大素數(譬如兩個百位素數)乘起來；反過來，要分解一不大整數(譬如200位)則幾乎不可能。(關於RSA體制的詳細介紹，請參閱文獻[1])。因此RSA體制就與素數判別和大數分解有密切聯系。首先，要具體建立一個RSA體制就需要兩個大素數，因而就涉及到尋找大素數的問題；而RSA體制的破譯之可能性就依賴於分解一個大數可能性。於是，RSA體制的建立與破譯就等價於素數判別與大數分解問題。近來，由於計算機科學的發展，人們對許多數學分支的理論體系重新用計算的觀點來討論。從計算的觀點來討論數論問題形成了當前很活躍的分支－—計算數論。而素數判別和大數分解成為這一分支的重要組成部分。在這一部分里提出了兩個重要的、懸而未決的問題：是否存在判別素數的多項式演算法？是否存在分解大整數的多項式演算法？已知道「分解整數」這個問題是一個NP完全問題，因此對上面第二個問題的討論是解決計算機科學中的難題：「NP完全問題是否一定是多項式演算法可解的？」的一個突破口。因此，素數判別和大數分解對計算機科學來說也是很有價值的。
最直接的素數判別和大數分解方法就是試除法，即對整數n，用2，…，n-1去試除，來判定n是否素數，分解式如何。這個方法是最簡單的一個方法，古希臘時就被人所知，但這個方法對較大的數(20位左右)就要耗費很多時間。在本世紀四十年代電子計算機出現之前，盡管產生了許多素數判別和大數分解方法，但因為用手算，速度太慢，很多方法在實用中即使對十幾位的數也需要好幾天，而對更大的數就無能為力了。隨著計算機的出現及發展，人們開始用這個有力的工具來研究素數判別和大數分解。到六十年代末期，已產生了許多新方法，歷史上的許多方法也得到了應用，使得對四十幾位數的素數判別可以很快得到結果。而到七十年代末，數論學家和計算機專家們已深入地研究了這個問題，得到許多實際有效的方法。用這些方法在較好的計算機上判別一個100位數是否素數只需不到一分鍾；分解70位左右的整數也是日常工作了。這些成果已引起人們的普遍關注。在這個領域中的研究空前活躍。雖然離問題的徹底解決還很遠，但在本領域中已取得了一個又一個的突破。在這方面的研究必有光輝的前景。
我們寫這個小冊子的目的是要介紹素數判別和大數分解的發展歷史、一般理論、各種方法及最新成果，是想讓許多非專業的讀者了解這個方向的內容和進展情況。當然，只有在這些定理的證明較為初等而又不太長時，我們才給出其證明。因為這個方向與計算機科學的密切關系，我們還要結合計算量來介紹一些數論中常用的基本演算法。
除了極個別內容，如第二章第七節，本書的絕大部分內容只需要某些初等數論的知識，它們可以在任何一本介紹初等數論的書中都能找到，如文獻[1] 。對於廣義黎曼猜想，我們寫了一則簡短的附錄。作為「世界數學名題欣賞叢書」中的一本，如果讀者在欣賞之餘，還打算進一步學習和探討的話，那麼，後面所列的文章和書目，可供參考。
限於水平，本書的缺點和錯誤一定不少，我們期待著讀者的批評指正。
1．演算法及其計算量的概念
通常，解決問題的方式有兩種．其一是對問題的每個對象(也稱作輸入)，直接給出答案，其二是給出一套規則，使得對問題的任何一個對象(輸入)，解答者可依照這些規則、機械地執行運算，能在有限步內得到答案．這里的第二種方式就是問題的演算法解答，這時也稱問題是演算法可解的，而所給出的規則就稱為演算法．
例 在復數范圍內解一元二次方程．這個問題的輸入即是具體給出的一元二次方程．任給一個方程種解答方式．
例 判別任意給出的自然數是否素數．
熟知，我們沒有象上例那樣的公式來表明哪個數是素數，哪個數不是素數．但是，我們可以以如下方式解答此問題：對任意給定的數n，用2，3 3，…，n－1去試除n，若其中有一個除盡n，則n不是素數；否則，n是素數．這就是問題的演算法解答．注意，演算法不可解的問題是存在的．希爾伯特的第十問題就是一個演算法不可解的問題．這一點是馬遞佳塞維奇於1970年證明的．
對演算法可解的問題而言，解答的演算法可能很多，我們在實際解決問題時究竟採取哪一種演算法呢？這就要求對演算法的好壞進行評判．演算法的好壞與所謂的計算量有密切關系．人們注意到，對某類問題的解答依賴於一些基本運算．譬如，在排序問題中，比較運算——即比較兩個元的先後——是一種基本運算．當然，「互換位置」也可以當作是一種基本運算．一個演算法在對問題的某個輸入解答所執行的基本運算次數，稱為演算法對此輸入執行的計算量．演算法對不同的輸入執行的計算量一般不同．在把計算量描述為輸入的函數之前，需要對輸入給個度量，這就是所謂的輸入尺寸．例如，在排序問題中，輸入尺寸可定義為待排序的貫的長度．這樣一來，計算量可以描述為輸入尺寸的函數．演算法對問題的所有輸入執行的計算量的最大值稱為演算法在最壞性態下的計算量．如果解決一個問題有兩個演算法，其中一個演算法在最壞性態下的計算量比另一個在最壞性態的計算量少，則稱前者在最壞性態下比後者好．若一個問題存在一個演算法解，其演算法在最壞性態下的計算量是輸入尺寸的多項式函數，則稱此問題存在多項式演算法，也說問題是P問題，否則稱它不存在多項式演算法．
最後，我們談談概率演算法和確定演算法。所謂概率演算法就是它的某些步驟是要依靠服從某種分布的隨機抽樣來完成的，這種隨機過程應是有限步內可完成的，而且演算法得出的結論應與所作的隨機抽樣無關，利用隨機手段僅僅是為了加快演算法的進程或為了方便．確定演算法是相對於概率演算法而言的，即它的每一步驟都是確定的，不須用隨機手段就可完成的．以後，這兩種演算法都會遇上，凡沒有用隨機手段的都是確定演算法，我們將不作特別說明了．
2．數論中的基本演算法
在數論問題中，輸入一般是一個或幾個自然數．如果輸入是一個自然數n，則定義其輸入尺寸為它的二進位表示的位數，即〔log2n〕 ＋1，有時也將log2n作為輸入尺寸．熟知，數論問題的解答中，自然數的加減乘除這四則運算是基本的運算，而兩個個位數的加法、減法和乘法及兩位數除以個位數的除法又最基本．因此，我們如下定義數論問題的基本運算：假如我們是在r－進位制中討論自然數的運算(通常在十進位下討論，即r=10；而在計算機上，一般在二進位下討論，即r=2)，則基本運算就是個位數的相加、相減、相乘，兩位數除以個位數的除法及向左移位運算(即乘上r)．有了基本運算，就可以來討論數論中的基本演算法了．
(1)四則運算加法：回憶一下小學里學多位數相加的情景，當時是列豎式再按老師教的規則去演算．這些豎式規則就是演算法．我們依照用豎式演算的步驟將其用文字寫出來即是：任意給定兩個n位的r進位數(如有一個沒夠n位，可添一些零而達到n位)．a=(an-1…a1a0)r=an-1rn-1+an-2rn-2+…+a1r+a0,ｂ=(bn-1…b1b0)r=bn-1rn-1+bn-2rn-2+…+b1r+b0， =c0r＋s0，其中0≤s0＜r，c0=0或1視a0＋b0＜r或≥r而定．接著有a1＋b1＋c0=c1r＋s1，0≤s1＜r，因為0≤c0≤1，0≤a1，b1≤r－1，故c1=0或1視a1＋b1＋c0＜r或≥r而定，繼續對第2，3，……，n－1討論得，存在c1，si使ai＋bi＋ci-1=ci·r＋si，其中0≤si＜r，ci=0或1(i=1，2，…，n－1)，最後令cn-1=sn，則因為由ai，bi，ci-1經帶余除法ai＋bi＋ci-1=cir＋si，0≤si＜r，ci=0或1確定ci，si至多需要5次基本運算，故用豎式演算法計算兩個n位數的計算量至多是5n，用O記號即是O(n)．在二進位制中，r=2，輸入n的位數是〔long2n〕+1，另外，對任意的r＞1有〔longrn〕+1=O〔long2n〕，故得到下面的定理．
定理1.1 用豎式演算法計算兩個不大於n的數相加時，其計算量是O〔long2n〕．減法：同加法一樣地討論，只是將a＋b、ai＋bi等改成a－b，ai－bi，相應地，ci=0或－1視ai－bi＋ci-1≥0或≤0而定．我們也可以得到下面的定理．定理1.2 用豎式演算法計算兩個不大於n的數相減時，其計算量是O(log2n)．乘法：在用豎式演算法作多位數的乘法時，先是做個位數與多位數相乘，然後再移位相加．於是，我們先來討論個位數與多位數相乘．設－2，依次有aib0+ci-1=cir+si，其中0≤si＜r，因為0≤ai，b0≤r－1，0≤ci-1≤r－2，故0≤aib0+ci-1≤r(r－2)+(r－１)，因而0≤ci≤r－2，以上i=1，…，n－1．再令sn=cn-1，則得ab= 因為(a·bi)ri是a·bi的r進位表示式向左移i位，即在a·bi的r進位表示式之後添i個零．因此表達式(1)表示m個數移位相加，這就將多位數乘法歸結為多位數與個位數相乘，然後再移位相加．
注意到，在個位數與多位數相乘時，由ai，bi，ci-1經aibi＋ci-1=cir＋si，0≤si＜r確定ci，si至多需要5次基本運算，故個位數與n位數相乘的計算量至多是5n，而(1)式表明，n位數與m位數相位數與n＋2位數、n＋2位數與n＋3位數、……、n＋m－1位數
式演算法做n位數與m位數(m≤n)相乘的計算量不多於13mn．設M(n)表示兩個n位數相乘的計算量，則M(n)=O(n2)．故可得下面的定理．
定理1.3 豎式演算法做兩個不超過n的數的相乘時，其計算量是O
帶余除法：帶余除法的豎式演算法要用文字表述出來比先前的加法和乘法都要麻煩，但它只不過是將小學里做帶余除法的過程詳細地寫出來而已，這里不準備重復這些枯燥的敘述，而只將帶余除法的豎式演算法的計算量寫出來．
定理1．4 用豎式演算法作兩個不超過n的數的帶余除法時，其計
實際上，我們是得到這樣的結論：一個2n位數除以一個n位數所得的商和余數的計算需要計算量O(n2)，之後，才有定理1.4．而且由此可得，對一個不超過m2的數a取模m得最小非剩餘的計算量是O(log22m)．
關於自然數的乘法，我們還想介紹兩個優美的結果，其證明已超出本書的范圍．定理1.5 任給一個正數ε，無論如何小，都存在一個乘法演算法，它做兩個n位數相乘的計算量是O(n1＋ε)，或者說，它做兩個不大於n的數相乘的計算量是O(log21＋εn)．
定理1.6 存在乘法演算法，使其作兩個n位數相乘的計算量是O(n·log2n·long2log2n)，或者說，它做兩個不大於n的數相乘的計算量是O(log2n·log2log2n·log2log2log2n)
定理1.6中的乘法所需的計算量被認為是作乘法運算的最優計算量，即不存在有更少計算量的乘法演算法．[2]
下面的定理表明，除法所需的計算量與乘法所需的計算量相當，它的證明也不在本書范圍內，讀者可參見[2].
定理1.7 存在除法演算法，它求一個2n位數除以一個n位數得的商和余數所需的計算量是O[M(n)]，其中M(n)是做兩個n位數乘法所需的計算量．
盡管定理1.5和定理1.6說明了有比豎式演算法快得多的乘法演算法，但為方便起見，我們以後還是使用豎式演算法的計算量來代表兩個數相乘的計算量．
(2)冪運算
給定一個整數a，由ak=a·ak-1，a1=a，歸納地定義了a的任意次冪．在素數判別和大數分解的討論中，我們常常遇到要計算anmod m．如果根據定義，先計算amod m，再依次計算akmod m=(amod m)·(ak-1mod m)mod m，則至少需要n次乘法才能得到anmod m，而n經常是很大很大，這時計算量也就很大，於是需要有更好的計算anmod m的方法．我們確實有更好的方法，先來看一個例子．
例 計算3107(mod 134)
將107寫成二進位數，即107=(1101011)2．我們有31≡3(mod 上例中的方法可以推廣到一般情況．當要計算an mod m時，先將n用二進位製表示，設n=(ak-1…a1a1)，ai=0或1，i=0，1，…，k－1． 再
再將使ai=1對應的ri連乘起來，取模m，則得akmod m(這里連乘是指每乘一個數取一次模m，然後用所得的結果再與另一乘數相乘)．我們有下面的定理
定理1.8 給定a，存在求冪取模的演算法，使得其計算anmodm的計算量為O(log2nlog22m)．
證明 在上面所描述的演算法中，r0=amod m．因為a是一個事先給定的常數，故r0的計算可以忽略．而ri=r2i-1mod m，i=1，…，n－1，因而計算每個ri的計算量是O(log22m)(其中，ri-1乘ri-1的計算量為O(log22mri-1)≤O(log22m)，取模m的計算量為O(log22m))，而這里k=〔log2n〕+1=O(log2n)，故計算r0，r1，…，rk-1的總共計算為O(log2n·log22m)．在把對應於ai=1的ri連乘起來時，每作一次乘法取一次模m，在這串連乘積中，乘法次數至多〔log2n〕＋1次，取模m的次數也至多〔log2n＋1〕次，而且每次乘法的兩個乘數都不超過m，故做連乘積的計算量是O(log2nlog22m)．因此，計算an modm總共需要計算量O(log2n log22m)．□
(3)努卡斯序列的項的計算．
所謂努卡斯序列是指其中α和β是以下整系數二次方程的根：x2－Px ＋Q=0，(P，Q)=1
在以後討論素數判別時，我們需要計算努卡斯序列的第n項取模m：Unmodm和Vnmodm．它們的計算可利用努卡斯序列的性質，象討論anmodm的計算一樣，得到比較好的演算法，因為討論它的基本思路與上一段一樣，且要用到努卡斯序列的一些較繁雜的性質．這里，我們只敘述一個結果，讀者有興趣可自己證明這個結果。
定理1.9 給定P、Q，(P，Q)=1，存在演算法使其計算Unmodm和Vnmodm的計算量是O(log2nlog22m)．(4)進位製表示的互化
我們常常需要將一個自然數的一種進位製表示化為另一種進位製表示．譬如，日常給出的自然數是十進位數，要將它輸到計算機中就必須將它化成二進位數，反過來，從計算機輸出的結果又要從二進位數化為十進位數，才能使常人看懂結果．
設自然數n，由r1進位制給出，要將它化為r2進位制，我們可以如下完成：在r1進位制體系中進行四則運算，特別是帶余除法運算，有則(qk-1qk-2…q1q0)r2便是n在r2進位制中的表達式．由帶余除法的計算量(見定理1.4)知，完成(2)的計算量是O(log23n)．
(5)最大公因數的演算法
求最大公因數的最普遍的演算法是歐幾里得演算法，它最初是公元前由歐幾里得提出來的，有時也稱它為輾轉相除法．表述如下：
設給定m，n(m＞n)，令r0=m，r1=n，有則得rk=gcd(rk-1，rk)=gcd(rk-2，rk-1)=…=gcd(r2，r3)=gcd(r1，r2)=gcd(r0，r1)=gcd(m，n)．歐幾里得演算法(3)中作帶余除法的次數k可由m和n確定出來．我們介紹下面的定理．
定理1.10 (3)式中的k＜5log2n＋1，即得輾轉相除的次數不大於n的十進位表示的位數的5倍．證明 引入斐波那契序列F0=0，F1=1，Fn=Fn-1＋Fn-2，n=2，rk≥1=F2，rk-1＞rk故rk-1≥rk＋1≥2=F3，rk-2≥rk-1＋rk≥＋1．設n的十進位數表示的位數是1，則有n＜101，故k＜51＋1，而k和51＋1都是整數，故k≤51．□
推論 用歐幾里得演算法求m，n(m≥n)的最大公因數的計算量是O(log23m)．
證明 因為(3)式中的k＜5log10n＋1，而且，其中每次帶余除法的被除數和除數都不大於m，故由定理1.4知，每次帶余除法的計算量是O(log22m)，再由定理1.10及n≤m即得，由(3)得到gcd(m，n)的計算量是O(log23m)．□
熟知，由(3)式的最後一個等式往回推演，可以得到u和v使gcd(m，n)=um ＋vn，而且計算出u，v的計算量也可以證明是O(log23m)，故對一次不定方程ax ＋by=c(其中gcd(a，b)|c)和一次同餘式ax≡c(modb)(gcd(a，b)| c)求解的計算量是O(log23m)，這里m=max(a，b，c)．
另外，為了以後的需要及其本身的重要性，我們要討論雅可比符
是可以顯然地得出的，故仍需要一個演算法．我們可以利用雅可比符號的兩點性質：寫出一個類似於歐幾里得演算法的演算法如下．
以下用e(x)表示自然數x的最高2因子的冪次，即2e(x)，2e(x)+1,用x＇表示x的最大奇因子，顯然有x=2e(x)．x＇．現在，給定兩個數m，n，這里m為奇數且設m＞n．令r0=m，r1=n，
則有其中r2=r0modr＇1，即r0除r′1得的余數．再將r2代換r1，r＇1代換r0重復(4)的手續，不斷地重復(4)的演算，最後得到r2=1
(m＞n)的計算量是O(log23m)．
(6)中國剩餘定理
定理 1.11 設m，…，mr(mi＞1)是兩兩互素的自然數，a1，…，ar是r個整數，M=m1…mr，則存在唯一的0≤a＜M使得a≡ai(modmi)i=1，…，r．且有演算法使得其計算a的計算量是O(r·log23M)．i=1，…，r；設a，b都滿足0≤a＜M，0≤b＜M，a≡ai(modmi)，b≡ai(modmi)(i=1，…，r)，即a－b≡0(modmi)，i=1，…，r，而m1，…，mr兩兩互素，因而a－b≡0(modM)，再由0≤a＜M，0≤b＜M即得a=b．於是唯一性證得．
按上面的方法計算a，先要計算M=m1…mr，因為m1…mi乘mi＋1的計算量是O(log2m1…mi·log2mi＋1)，故計算M的計算量是O
同樣，計算Mi的計算量也不多於O(log22M)．由上一段的討論，求得ui的計算量是O(log23Mi)≤O(log23M)．最後，由ui，Mi，ai計算a的計算量也是O(log23M)，因而求a的總計算量是O(rlog32M)．□
關於數論中的基本演算法的研究，是計算數論的最基本的研究，不僅是它本身很重要，它在很多其它分支如計算機科學、代數學等中有很大的用處．然而到目前為止，除了有些文章散見於某些雜志和書籍中，還沒有較完全的書來專門討論這些問題．在這一方面，最好的文章是勒默的「計算機技巧應用於數論」.

㈨ 判斷一個整數是不是素數的演算法

建立一個素數表（一般不大於此整數的算術平方根即可）進行試除，或者利用一些常見素數性質，以及被素數整除的性質來判斷