java做二个数的最大公约数_百度知道.htm

你好这是怎么求三个数的最大公约数和最小公倍数

<DIV class=p90>
<DIV class="f14 B wr" id=question_title><CQ>java做二个数的最大公约数</CQ></DIV>
<DIV class=wr id=question_info><SPAN class=red><IMG height=16 
src="java做二个数的最大公约数_百度知道.files/icn_point.gif" width=16 align=absMiddle> 
悬赏分：5</SPAN> - <SPAN class=gray>解决时间：2006-4-7 19:26</SPAN></DIV>
<DIV class="f14 wr" id=question_content><CD>帮我做一个程序~~ <BR>就是二个数的最大公约数要用JAVA做~~~ 
<BR>还要在KEY上输入~~~帮我还可以得五分啊~~ <BR>又对自己学习有好处~~可以加我的QQ6736426 <BR>要说明加我的原因~~~ 
<BR>还要满足任何数~~~我做的不大满意~~~</CD></DIV>
<DIV class="f14 wr" id=question_sup></DIV></DIV>
<DIV class="gray wr" id=question_author align=right>提问者： <A 
href="http://passport.baidu.com/?business&amp;aid=6&amp;un=jingmachao#2" 
target=_blank>jingmachao</A> - <A 
href="http://www.baidu.com/search/zhidao_help.html#n5" target=_blank>试用期 一级</A> 
</DIV></DIV></DIV>
<DIV class=rg_4></DIV>
<DIV class=rg_5></DIV>
<DIV class=rg_1></DIV></DIV>
<DIV class="mb12 bai">
<DIV class=rr_1></DIV>
<DIV class=rr_2></DIV>
<DIV class=rr_3></DIV>
<DIV class=rr>
<DIV class=t1>
<DIV class=ico>
<DIV class=ibest></DIV></DIV>最佳答案</DIV>
<DIV class=bc0 
style="PADDING-RIGHT: 0pt; PADDING-LEFT: 0pt; PADDING-BOTTOM: 5px; PADDING-TOP: 5px">
<DIV class=wr>
<DIV class="f14 p90 pl10" id=best_answer_content><CA>1、欧几里德算法和扩展欧几里德算法 
<BR><BR>欧几里德算法 <BR>欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： 
<BR><BR>定理：gcd(a,b) = gcd(b,a mod b) <BR><BR>证明：a可以表示成a = kb + r，则r = a mod b 
<BR>假设d是a,b的一个公约数，则有 <BR>d|a, d|b，而r = a - kb，因此d|r <BR>因此d是(b,a mod b)的公约数 
<BR><BR>假设d 是(b,a mod b)的公约数，则 <BR>d | b , d |r ，但是a = kb +r <BR>因此d也是(a,b)的公约数 
<BR><BR>因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证 
<BR><BR>欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为： <BR><BR>void swap(int &amp; a, int &amp; 
b) <BR>{ <BR>int c = a; <BR>a = b; <BR>b = c; <BR>} <BR>int gcd(int a,int b) 
<BR>{ <BR>if(0 == a ) <BR>{ <BR>return b; <BR>} <BR>if( 0 == b) <BR>{ <BR>return 
a; <BR>} <BR>if(a &gt; b) <BR>{ <BR>swap(a,b); <BR>} <BR>int c; <BR>for(c = a % 
b ; c &gt; 0 ; c = a % b) <BR>{ <BR>a = b; <BR>b = c; <BR>} <BR>return b; <BR>} 
<BR><BR>2、Stein算法 
<BR>欧几里德算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。 
<BR><BR>考虑现在的硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。 
<BR><BR>Stein算法由J. Stein 1961年提出，这个方法也是计算两个数的最大公约数。和欧几里德算法 
算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。 <BR><BR>为了说明Stein算法的正确性，首先必须注意到以下结论： 
<BR><BR>gcd(a,a) = a，也就是一个数和他自身的公约数是其自身 <BR>gcd(ka,kb) = k 
gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除 <BR><BR>C++/java 实现 
<BR>// c++/java stein 算法 <BR>int gcd(int a,int b){ <BR>if(a&lt;b)//arrange so 
that a&gt;b{ <BR>int temp = a; <BR>a = b; <BR>b=temp; <BR>} <BR>if(0==b)//the 
base case <BR>return a; <BR>if(a%2==0 &amp;&amp; b%2 ==0)//a and b are even 
<BR>return 2*gcd(a/2,b/2); <BR>if ( a%2 == 0)// only a is even <BR>return 
gcd(a/2,b); <BR>if ( b%2==0 )// only b is even <BR>return gcd(a,b/2); 
<BR><BR>return gcd((a+b)/2,(a-b)/2);// a and b are odd <BR><BR>}</CA><BR>参考资料：<A 
href="http://blog.programfan.com/trackback.asp?id=3007" 
target=_blank>http://blog.programfan.com/trackback.asp?id=3007</A></DIV>
<DIV class=gray id=best_answer_info style="MARGIN: 5px" align=right>回答者： <A 
href="http://passport.baidu.com/?business&amp;aid=6&amp;un=hefangshi#2" 
target=_blank>hefangshi</A> -<A 
href="http://www.baidu.com/search/zhidao_help.html#n5" target=_blank> 见习魔法师 
二级</A><SPAN id=im-user-cde9686566616e67736869b200 title=hefangshi>&nbsp;</SPAN> 
<SPAN id=best_answer_time>3-27 20:50</SPAN></DIV>
<DIV style="MARGIN: 5px; TEXT-ALIGN: right"><A 
href="http://zhidao.baidu.com/remark/5399863.html" 
target=_blank>我来评论&gt;&gt;</A></DIV>
<DIV class=t2>提问者对于答案的评价：</DIV>
<DIV class="p90 pl10 f14" id=best_answer_comment>恩！！书上的~~</DIV>
<DIV class=t2>评价已经被关闭&nbsp;&nbsp;&nbsp;&nbsp;<SPAN class="f12 gray" 
style="FONT-WEIGHT: normal">目前有 1 个人评价</SPAN></DIV>
<DIV class=pl10>
<FORM name=fpj action=/q method=post>
<TABLE cellSpacing=0 cellPadding=0 border=0>
  <TBODY>
  <TR vAlign=top><INPUT type=hidden value=22 name=ct> <INPUT type=hidden 
    name=mpn> <INPUT type=hidden value=100003 name=cm> <INPUT type=hidden 
    value=5399863 name=qid> <INPUT type=hidden value=iksubmit name=tn> <INPUT 
    type=hidden value=/question/5399863.html name=lu>
    <SCRIPT>function g(w){ document.fpj.mpn.value=w;};document.fpj.lu.value=escape(location.href)</SCRIPT>
     
    <TD class=f14 width=120>好<BR><SPAN class=red>100%</SPAN> （1）</TD>
    <TD class=f14 width=120>不好<BR><SPAN class=grn>0% 
</SPAN>（0）</TD></TR></TBODY></TABLE></FORM></DIV></DIV></DIV></DIV>
<DIV class=rr_4></DIV>
<DIV class=rr_5></DIV>
<DIV class=rr_1></DIV></DIV><A name=irelatelink></A>
<DIV class="mb12 bai">
<DIV class=rg_1></DIV>
<DIV class=rg_2></DIV>
<DIV class=rg_3></DIV>
<DIV class=rg>
<DIV class=t1>
<DIV class=ico>
<DIV class=irelate></DIV></DIV>相关内容</DIV>
<DIV class=bc0 id=relate_question>
<TABLE class=relateTable id=qbRelateTable cellSpacing=0 cellPadding=0 
  border=0><TBODY id=qbRelateTableBody>
  <TR>
    <TD class=gray vAlign=top width=10>&#8226; </TD>
    <TD class=f14><A 
      href="http://zhidao.baidu.com/question/8016911.html?fr=qrl" 
      target=_blank><CR>怎样用java做二个数的最大公约数 ?</CR></A></TD></TR>
  <TR>
    <TD class=gray vAlign=top width=10>&#8226; </TD>
    <TD class=f14><A 
      href="http://zhidao.baidu.com/question/52227387.html?fr=qrl" 
      target=_blank><CR>java最大公约数算法</CR></A></TD></TR>
  <TR>
    <TD class=gray vAlign=top width=10>&#8226; </TD>
    <TD class=f14><A 
      href="http://zhidao.baidu.com/question/72517738.html?fr=qrl" 
      target=_blank><CR>JAVA面向对象编程的试题谁有？</CR></A></TD></TR>
  <TR>
    <TD class=gray vAlign=top width=10>&#8226; </TD>
    <TD class=f14><A 
      href="http://zhidao.baidu.com/question/59631702.html?fr=qrl" 
      target=_blank><CR>求java练习题</CR></A></TD></TR>
  <TR>
    <TD class=gray vAlign=top width=10>&#8226; </TD>
    <TD class=f14><A 
      href="http://zhidao.baidu.com/question/55281466.html?fr=qrl" 
      target=_blank><CR>几个JAVA的小程序，很简单，大家帮帮忙！谢谢了！</CR></A></TD></TR>
  <TR id=moreRelateQuestion>