算法分析與設(shè)計課程設(shè)計實驗報告求最大公約數(shù)實驗報告實驗（含源程序）

1、昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告（ 2011 2012 學(xué)年 第 1 學(xué)期 ）課程名稱：算法分析與設(shè)計 開課實驗室：信自樓機房445 2011 年10月 12日年級、專業(yè)、班計科092學(xué)號200910405201姓名劉召成績實驗項目名稱求最大公約數(shù)指導(dǎo)教師 張晶教師評語該同學(xué)是否了解實驗原理：a.了解b.基本了解c.不了解該同學(xué)的實驗?zāi)芰Γ篴.強 b.中等 c.差 該同學(xué)的實驗是否達到要求：a.達到b.基本達到c.未達到實驗報告是否規(guī)范：a.規(guī)范b.基本規(guī)范c.不規(guī)范實驗過程是否詳細記錄：a.詳細b.一般 c.沒有 教師簽名： 年 月 日一、上機目的及內(nèi)容上機內(nèi)容求兩個自然數(shù)m和n

2、的最大公約數(shù)。上機目的（1）復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識，實現(xiàn)課程間的平滑過渡；（2）掌握并應(yīng)用算法的數(shù)學(xué)分析和后驗分析方法；（3）理解這樣一個觀點：不同的算法能夠解決相同的問題，這些算法的解題思路不同，復(fù)雜程度不同，解題效率也不同。二、實驗原理及基本技術(shù)路線圖（方框原理圖或程序流程圖）（1）至少設(shè)計出三個版本的求最大公約數(shù)算法；所設(shè)計的3個版本分別是：連續(xù)整數(shù)檢測算法、歐幾里得算法和分解質(zhì)因數(shù)算法。這3 個算法的流程圖分別如下所示：（2） 對所設(shè)計的算法采用大o符號進行時間復(fù)雜性分析；在連續(xù)整數(shù)檢測算法中，由于其最壞的情況是m與n除以t均不為0，直到t接近于0為止，此時所需時間接近m和n的較小

3、者的值；在歐幾里得算法中，最壞的情況是每次所得的都比n略小一點；但此時，它的數(shù)據(jù)還是以n倍遞減；在分解質(zhì)因數(shù)算法中，關(guān)鍵是分解質(zhì)因數(shù)的時間復(fù)雜度和將所得質(zhì)因數(shù)相乘合并的時間復(fù)雜度；在對m和n分解質(zhì)因數(shù)時，最壞的情況是m和n的質(zhì)因數(shù)都還是m和n；分解m和n用的時間復(fù)雜度是： ；對于所得到的質(zhì)因數(shù)求出它們的公共質(zhì)因數(shù)時最壞的情況是有較多的質(zhì)因數(shù)，且兩組質(zhì)因數(shù)之間沒有公共質(zhì)因數(shù)，此時時間復(fù)雜度是兩組質(zhì)因數(shù)數(shù)目之平方；然而，對于所得到的質(zhì)因數(shù)數(shù)量極為有限，因此對于最壞情況下的m和n的分解質(zhì)因數(shù)，所得到的質(zhì)因數(shù)的數(shù)量就更少，此時可以把對于質(zhì)因數(shù)合并得公共質(zhì)因數(shù)的時間復(fù)雜度忽略不計；最壞的時間復(fù)雜度是：（

4、3） 上機實現(xiàn)算法，并用計數(shù)法和計時法分別測算算法的運行時間；在我的電腦測試所得到的部分數(shù)據(jù)表格：連續(xù)整數(shù)檢測時間（秒）歐幾里得時間（秒）分解質(zhì)因數(shù)時間（秒）最大公約數(shù)673153380921974453701298.50032162139311656621917842814657010.9200.0011302111111177779777773284650.09900.016111111111777771113684845470.93400.15423137137137137133544513714.26708.8731234137137317311234567891.53504.0421

5、346546133132197454137911.45300.0616545874874654687874345354548454.199056.386287987465468998654658480.821013.7182545487434354313213556.937048.904154446846464645365534546350.7700.032564646546546546546446132544550.21200.0051544646846553356353253.932024.06155154654654235112436428.01303.86925546464664654

6、64687313212135143.06200.23135454546363369321329432738.99600.1323平均使用時間19.040625010.03更多測試數(shù)據(jù)請參見附錄：數(shù)據(jù)測試清單！也可運行程序： 兩個正整數(shù)最大公約數(shù)求解簡易系統(tǒng)(32位).exe自己進行數(shù)據(jù)測試。（4） 通過分析對比，得出自己的結(jié)論。通過以上可以得知，歐幾里得算法的性能最優(yōu)，而分解質(zhì)因數(shù)算法和連續(xù)整數(shù)檢測算法的效率差不多，但是，當兩個數(shù)據(jù)相差很大時，連續(xù)整數(shù)檢測算法可能會比分解質(zhì)因數(shù)算法占優(yōu)勢；當兩個數(shù)所得到的最大質(zhì)因數(shù)都較小時，分解質(zhì)因數(shù)算法可能比連續(xù)整數(shù)檢測算法占優(yōu)勢。三、所用儀器、材料（設(shè)備名

7、稱、型號、規(guī)格等或使用軟件）1臺pc及visual studio 2005軟件四、實驗方法、步驟（或：程序代碼或操作過程）/ 兩個正整數(shù)最大公約數(shù)求解簡易系統(tǒng).cpp : 定義控制臺應(yīng)用程序的入口點。/*該系統(tǒng)是為了計算兩個正整數(shù)的最大公約數(shù)*該系統(tǒng)是在visual studio 2005環(huán)境下編輯的，并通過visual studio 2005環(huán)境下編譯與運行*該版本使用了boost函數(shù)庫中的timer.hpp庫函數(shù)，關(guān)于boost函數(shù)庫可以參考網(wǎng)絡(luò)上的boost社區(qū)*該程序制作人劉召*該系統(tǒng)創(chuàng)建時間是2011年10月12日*/#include stdafx.h#include#include

8、#include#include#include#include using namespace std;using namespace boost;long long smallernumber(long long i,long long j)return ij?i:j;long long cheking(long long m,long long n,long long t)if(m%t)-t;return cheking(m,n,t);if(n%t)-t;return cheking(m,n,t);return t;void gcdintegerchecking(long long m,

9、long long n,long long *p)long long t=smallernumber(n,m); *p=cheking(m,n,t);void gcdoujilide(long long m,long long n,long long *p)long long t=m,s=n;long long r=m%n;while(r!=0)m=n;n=r;r=m%n;*p=n;void zhiyinshupanduan(long long i,list& list)long long x=(long long)(i/2),j=i;for(long long g=2;g=x;g+)whil

10、e(i%g=0)list.push_back(g);i/=g;x=(long long)(i/2);if(i!=1)list.push_back(i);void gcdfenjiezhiyinshu(long long m,long long n,long long *p,list*list1,list*list2,list*plist)long long count=1;zhiyinshupanduan(m,*list1);zhiyinshupanduan(n,*list2);list:iterator it,rt,yt,gt=(*list2).begin();for(it=(*list1)

11、.begin();it!=(*list1).end();it+)long long a=1,b=1;yt=it;yt+;while(yt!=(*list1).end()&*yt=*it)yt+;a+;it+;for(rt=gt;rt!=(*list2).end();rt+)if(*it=*rt)gt=rt;gt+;while(gt!=(*list2).end()&*gt=*rt)gt+;b+;for(long long h=0;hpush_back(*it);break;*p=count;void menu1()coutendlt1用連續(xù)整數(shù)檢測算法進行運算!t;cout2用歐幾里得算法進行運

12、算!endl;coutt3用分解質(zhì)因數(shù)算法進行運算!t;cout4結(jié)束對這兩個數(shù)的運算！endl;cout$：flush;void input(long long& m,long long& n)coutendl$：;cinm;cout$：;cinn;void menu()coutendlt1進行下一對整數(shù)最大公約數(shù)運算！t;cout2退出本系統(tǒng)！endl;cout$：flush;void welcome()coutnttt歡迎使用求解兩個正整數(shù)最大公約數(shù)的簡易系統(tǒng)nendl;couttttt學(xué) 校：昆明理工大學(xué)endl;couttttt學(xué) 院：信息工程與自動化學(xué)院endl;couttttt專

13、 業(yè)：計算機科學(xué)與技術(shù)endl;couttttt指導(dǎo)老師：張晶endl;couttttt制作人：劉召endl;couttttt學(xué) 號：endl;coutttttqq 郵箱：endl;void exitsystem()coutn你已經(jīng)成功退出本系統(tǒng)！n謝謝你的使用！再見！endl;void showzhiyinshu(long long j,list&list)if(list.size()coutendl整數(shù)j共有l(wèi)ist.size()個質(zhì)數(shù)，它們分別是：endl;elsecoutendl整數(shù)j沒有質(zhì)數(shù)！endl;list:iterator it;for(it=list.begin();it!=

14、list.end();it+)cout*itt;coutendl;list.clear();void showcommonnumber(long long m,long long n,list&plist)if(plist.size()coutendl整數(shù)m和n共有plist.size()個公共質(zhì)數(shù)，它們分別是：endl;elsecoutendl整數(shù)m和n沒有公共質(zhì)數(shù)！endl;list:iterator it;for(it=plist.begin();it!=plist.end();it+)cout*itt;coutk;coutendl;list list1,list2,plist;syst

15、em(color 2b);while(k0&k4)switch(k)case 1:timecountor.restart();gcdintegerchecking(m,n,&p);cout連續(xù)整數(shù)檢測算法所用時間為：timecountor.elapsed()秒(最高精確度毫秒級)endl;cout經(jīng)連續(xù)整數(shù)檢測算法運算所得m和n的最大公約數(shù)是：pendl;break;case 2:timecountor.restart();gcdoujilide(m,n,&p);cout歐幾里得算法所用時間為：timecountor.elapsed()秒(最高精確度毫秒級)endl;cout經(jīng)歐幾里得算法運算

16、所得m和n的最大公約數(shù)是：pendl;break;case 3:timecountor.restart();gcdfenjiezhiyinshu(m,n,&p,&list1,&list2,&plist);cout分解質(zhì)因數(shù)算法所用時間為：timecountor.elapsed()秒(最高精確度毫秒級)endl;showzhiyinshu(m,list1);showzhiyinshu(n,list2);showcommonnumber(m,n,plist);cout經(jīng)分解質(zhì)因數(shù)算法運算所得m和n的最大公約數(shù)是：pk;coutk;coutn你本次用時共time.elapsed()秒$：346546

17、1331321請輸入你所要運算的第二個整數(shù)$：974541379 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：1連續(xù)整數(shù)檢測算法所用時間為：11.453秒(最高精確度毫秒級)經(jīng)連續(xù)整數(shù)檢測算法運算所得3465461331321和974541379的最大公約數(shù)是：1 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經(jīng)歐幾里得算法運算所得3465461331321和9745413

18、79的最大公約數(shù)是：1 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：3分解質(zhì)因數(shù)算法所用時間為：0.06秒(最高精確度毫秒級)整數(shù)3465461331321共有4個質(zhì)數(shù)，它們分別是：3 11 18149 5786213整數(shù)974541379共有3個質(zhì)數(shù)，它們分別是：7 43 3237679整數(shù)3465461331321和974541379沒有公共質(zhì)數(shù)！經(jīng)分解質(zhì)因數(shù)算法運算所得3465461331321和974541379的最大公約數(shù)是：1 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解

19、質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：4 1進行下一對整數(shù)最大公約數(shù)運算！ 2退出本系統(tǒng)！請輸入你的選擇$：1請輸入你所要運算的第一個整數(shù)$：6731533809請輸入你所要運算的第二個整數(shù)$：219744537012 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：1連續(xù)整數(shù)檢測算法所用時間為：98.5秒(最高精確度毫秒級)經(jīng)連續(xù)整數(shù)檢測算法運算所得6731533809和219744537012的最大公約數(shù)是：3216213 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算!

20、 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經(jīng)歐幾里得算法運算所得6731533809和219744537012的最大公約數(shù)是：3216213 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：3分解質(zhì)因數(shù)算法所用時間為：0秒(最高精確度毫秒級)整數(shù)6731533809共有11個質(zhì)數(shù)，它們分別是：3 3 3 7 7 7 11 13 13 1723整數(shù)219744537012共有13個質(zhì)數(shù)，它們分別是：2 2 3 3 3 7 7 11

21、13 1719 29 31整數(shù)6731533809和219744537012共有8個公共質(zhì)數(shù)，它們分別是：3 3 3 7 7 11 13 17經(jīng)分解質(zhì)因數(shù)算法運算所得6731533809和219744537012的最大公約數(shù)是：3216213 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：4 1進行下一對整數(shù)最大公約數(shù)運算！ 2退出本系統(tǒng)！請輸入你的選擇$：1請輸入你所要運算的第一個整數(shù)$：931165662請輸入你所要運算的第二個整數(shù)$：19178428146570 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾

22、里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：1連續(xù)整數(shù)檢測算法所用時間為：10.92秒(最高精確度毫秒級)經(jīng)連續(xù)整數(shù)檢測算法運算所得931165662和19178428146570的最大公約數(shù)是：1302 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經(jīng)歐幾里得算法運算所得931165662和19178428146570的最大公約數(shù)是：1302 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解

23、質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：3分解質(zhì)因數(shù)算法所用時間為：0.001秒(最高精確度毫秒級)整數(shù)931165662共有7個質(zhì)數(shù)，它們分別是：2 3 7 31 73 97 101整數(shù)19178428146570共有10個質(zhì)數(shù)，它們分別是：2 3 3 5 7 11 11 31 919 8831整數(shù)931165662和19178428146570共有4個公共質(zhì)數(shù)，它們分別是：2 3 7 31經(jīng)分解質(zhì)因數(shù)算法運算所得931165662和19178428146570的最大公約數(shù)是：1302 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行

24、運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：4 1進行下一對整數(shù)最大公約數(shù)運算！ 2退出本系統(tǒng)！請輸入你的選擇$：1請輸入你所要運算的第一個整數(shù)$：1111111777797777請輸入你所要運算的第二個整數(shù)$：7328465 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：1連續(xù)整數(shù)檢測算法所用時間為：0.099秒(最高精確度毫秒級)經(jīng)連續(xù)整數(shù)檢測算法運算所得1111111777797777和7328465的最大公約數(shù)是：1 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法

25、進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經(jīng)歐幾里得算法運算所得1111111777797777和7328465的最大公約數(shù)是：1 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：3分解質(zhì)因數(shù)算法所用時間為：0.016秒(最高精確度毫秒級)整數(shù)1111111777797777共有6個質(zhì)數(shù)，它們分別是：3 3 7 223 93251 848123整數(shù)7328465共有2個質(zhì)數(shù)，它們分別是：5 1465693整數(shù)1111111777797777和7328

26、465沒有公共質(zhì)數(shù)！經(jīng)分解質(zhì)因數(shù)算法運算所得1111111777797777和7328465的最大公約數(shù)是：1 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：4 1進行下一對整數(shù)最大公約數(shù)運算！ 2退出本系統(tǒng)！請輸入你的選擇$：1請輸入你所要運算的第一個整數(shù)$：11111111777771113請輸入你所要運算的第二個整數(shù)$：68484547 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：1連續(xù)整數(shù)檢測算法所用時間為：0.9

27、34秒(最高精確度毫秒級)經(jīng)連續(xù)整數(shù)檢測算法運算所得11111111777771113和68484547的最大公約數(shù)是：23 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經(jīng)歐幾里得算法運算所得11111111777771113和68484547的最大公約數(shù)是：23 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：3分解質(zhì)因數(shù)算法所用時間為：0.154秒(最高精確度毫秒級)整數(shù)

28、11111111777771113共有4個質(zhì)數(shù)，它們分別是：23 1033 20233 23113679整數(shù)68484547共有3個質(zhì)數(shù)，它們分別是：23 79 37691整數(shù)11111111777771113和68484547共有1個公共質(zhì)數(shù)，它們分別是：23經(jīng)分解質(zhì)因數(shù)算法運算所得11111111777771113和68484547的最大公約數(shù)是：23 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：4 1進行下一對整數(shù)最大公約數(shù)運算！ 2退出本系統(tǒng)！請輸入你的選擇$：1請輸入你所要運算的第一個整數(shù)$：13

29、713713713713請輸入你所要運算的第二個整數(shù)$：354451371 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：1連續(xù)整數(shù)檢測算法所用時間為：4.267秒(最高精確度毫秒級)經(jīng)連續(xù)整數(shù)檢測算法運算所得13713713713713和354451371的最大公約數(shù)是：3 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經(jīng)歐幾里得算法運算所得13713713713713和3

30、54451371的最大公約數(shù)是：3 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：3分解質(zhì)因數(shù)算法所用時間為：8.87秒(最高精確度毫秒級)整數(shù)13713713713713共有4個質(zhì)數(shù)，它們分別是：3 13 263 1337010209整數(shù)354451371共有3個質(zhì)數(shù)，它們分別是：3 5419 21803整數(shù)13713713713713和354451371共有1個公共質(zhì)數(shù)，它們分別是：3經(jīng)分解質(zhì)因數(shù)算法運算所得13713713713713和354451371的最大公約數(shù)是：3 1用連續(xù)整數(shù)檢測算法進行運算!

31、 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：4 1進行下一對整數(shù)最大公約數(shù)運算！ 2退出本系統(tǒng)！請輸入你的選擇$：1請輸入你所要運算的第一個整數(shù)$：123413713731731請輸入你所要運算的第二個整數(shù)$：123456789 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：1連續(xù)整數(shù)檢測算法所用時間為：1.535秒(最高精確度毫秒級)經(jīng)連續(xù)整數(shù)檢測算法運算所得123413713731731和123456789的最大公約數(shù)是：1 1用連續(xù)整數(shù)檢測算法進

32、行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經(jīng)歐幾里得算法運算所得123413713731731和123456789的最大公約數(shù)是：1 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：3分解質(zhì)因數(shù)算法所用時間為：4.042秒(最高精確度毫秒級)整數(shù)123413713731731共有2個質(zhì)數(shù)，它們分別是：202343 609923317整數(shù)123456789共有4個質(zhì)數(shù)，它們分別是：3 3 3607

33、 3803整數(shù)123413713731731和123456789沒有公共質(zhì)數(shù)！經(jīng)分解質(zhì)因數(shù)算法運算所得123413713731731和123456789的最大公約數(shù)是：1 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：4 1進行下一對整數(shù)最大公約數(shù)運算！ 2退出本系統(tǒng)！請輸入你的選擇$：1請輸入你所要運算的第一個整數(shù)$：6545874874654687874請輸入你所要運算的第二個整數(shù)$：3453545484 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這

34、兩個數(shù)的運算！請輸入你的選擇$：1連續(xù)整數(shù)檢測算法所用時間為：54.199秒(最高精確度毫秒級)經(jīng)連續(xù)整數(shù)檢測算法運算所得6545874874654687874和3453545484的最大公約數(shù)是：2 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經(jīng)歐幾里得算法運算所得6545874874654687874和3453545484的最大公約數(shù)是：2 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！

35、請輸入你的選擇$：3分解質(zhì)因數(shù)算法所用時間為：56.386秒(最高精確度毫秒級)整數(shù)6545874874654687874共有6個質(zhì)數(shù)，它們分別是：2 23 37 41 11657 8047064651整數(shù)3453545484共有7個質(zhì)數(shù)，它們分別是：2 2 3 3 3 3 10659091整數(shù)6545874874654687874和3453545484共有1個公共質(zhì)數(shù)，它們分別是：2經(jīng)分解質(zhì)因數(shù)算法運算所得6545874874654687874和3453545484的最大公約數(shù)是：2 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的

36、運算！請輸入你的選擇$：4 1進行下一對整數(shù)最大公約數(shù)運算！ 2退出本系統(tǒng)！請輸入你的選擇$：1請輸入你所要運算的第一個整數(shù)$：87987465468998請輸入你所要運算的第二個整數(shù)$：65465848 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：1連續(xù)整數(shù)檢測算法所用時間為：0.821秒(最高精確度毫秒級)經(jīng)連續(xù)整數(shù)檢測算法運算所得87987465468998和65465848的最大公約數(shù)是：2 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的

37、運算！請輸入你的選擇$：2歐幾里得算法所用時間為：0秒(最高精確度毫秒級)經(jīng)歐幾里得算法運算所得87987465468998和65465848的最大公約數(shù)是：2 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：3分解質(zhì)因數(shù)算法所用時間為：13.718秒(最高精確度毫秒級)整數(shù)87987465468998共有4個質(zhì)數(shù)，它們分別是：2 43 503 2034016031整數(shù)65465848共有6個質(zhì)數(shù)，它們分別是：2 2 2 7 41 28513整數(shù)87987465468998和65465848共有1個公共質(zhì)數(shù)，它們分別是：2經(jīng)分解質(zhì)因數(shù)算法運算所得87987465468998和65465848的最大公約數(shù)是：2 1用連續(xù)整數(shù)檢測算法進行運算! 2用歐幾里得算法進行運算! 3用分解質(zhì)因數(shù)算法進行運算! 4結(jié)束對這兩個數(shù)的運算！請輸入你的選擇$：4 1進行下一對整數(shù)最大公約數(shù)運算！ 2退出本