判断质数算法

㈠ 判断一个数是不是质数的算法,流程图

是不是偶数（除了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)．□
关于数论中的基本算法的研究，是计算数论的最基本的研究，不仅是它本身很重要，它在很多其它分支如计算机科学、代数学等中有很大的用处．然而到目前为止，除了有些文章散见于某些杂志和书籍中，还没有较完全的书来专门讨论这些问题．在这一方面，最好的文章是勒默的“计算机技巧应用于数论”.

㈨ 判断一个整数是不是素数的算法

建立一个素数表（一般不大于此整数的算术平方根即可）进行试除，或者利用一些常见素数性质，以及被素数整除的性质来判断