编程实现下列算法：计算两个整数m、n的最大公约数gcd(m,n)算法1：欧几里得算法第一步：如果n=0，返回m的值作为结果，同时过程结束；否则，进入第二步。第二步：m除以n，将余数赋给r。第三步：将n的值赋给m，将r的值赋给n，返回第一步。#include<stdio.h>intgcd(intm,intn){if(m<n)returngcd(n,m);elseif(n==0)returnm;elsereturngcd(n,m%n);}main(){intm,n;scanf("%d%d",&m,&n);printf("最大公约数：%d\n",gcd(m,n));}算法2：连续整数检测算法第一步：将min(m,n)的值赋给t。第二步：m除以t，如果余数为0，进入第三步；否则，进入第四步。第三步：n除以t，如果余数为0，返回t的值作为结果；否则，进入第四步。第四步：把t的值减1。返回第二步。#include<stdio.h>intgcd(intm,intn){intt;if(m<n)t=m;elset=n;for(t=n;t>=1;t--){if(m%t==0&&n%t==0)break;}returnt;}main(){intm,n,t;scanf("%d%d",&m,&n);printf("最大公约数：%d\n",gcd(m,n));}算法3：公共质因数相乘算法第一步：找出m的所有质因数。第二步：找出n的所有质因数。第三步：从第一步和第二步求得的质因数分解式中找出所有的公因数（如果p是一个公因数，而且在m和n的质因数分解式中分别出现过pm和pn次，那么应该将p重复min{pm，pn}次）。第四步：将第三步中找到的质因数相乘，其结果作为给定数字的最大公约数。（1）找出n以内(包括n)的所有质数，结果存在一个List中publicstaticList<Integer>primeList(intn){List<Integer>prime=newArrayList<Integer>();//将2-n之间的所有自然数放进List.for(inti=2;iprime.add(i);intend=(int)Math.sqrt(n);//将非质数从Llist中去掉for(inti=2;iif(prime.indexOf(i)==-1)continue;for(intj=prime.indexOf(i)+1;j<prime.size();j++){if(prime.get(j)%i==0)prime.remove(j);}}returnprime;}（2）找出正整数n的所有质因数，放进一个List中publicstaticList<Integer>primeDivisorList(intn){List<Integer>prime=primeList(n/2);//只需要前n/2个质数List<Integer>primeDivisor=newArrayList<Integer>();inti=0;while(true){if(n==1)break;if(n%prime.get(i)==0){primeDivisor.add(prime.get(i));n=n/prime.get(i);i=0;//因为一个数可以有多个相同的质因数，所以要再从头寻找}elsei++;}returnprimeDivisor;}（3）找出公因数相乘，求两个数的最大公约数publicstaticintgcd3(intm,intn){intresult=1;List<Integer>mList=primeDivisorList(m);List<Integer>nList=primeDivisorList(n);while(!mList.isEmpty()&&!nList.isEmpty()){inti;for(i=0;i<nList.size();i++){if(mList.get(0)==nList.get(i)){//每找到一个公因数，将该数从两个公因数列表中删除mList.remove(i);result=result*nList.remove(i);break;}}if(i==nList.size())if(!mList.isEmpty())mList.remove(0)}returnresult;}