$("#ray_6234").html("\n
1<\/a>
2<\/a>
3<\/a>
4<\/a>
5<\/a>
6<\/a>
7<\/a>
8<\/a>
9<\/a>
10<\/a><\/strong>
11<\/a>
12<\/a>
13<\/a>
14<\/a>
15<\/a>
16<\/a>
17<\/a>
18<\/a>
19<\/a>
20<\/a><\/strong>
21<\/a>
22<\/a>
23<\/a>
24<\/a>
25<\/a>
26<\/a>
27<\/a>
28<\/a>
29<\/a>
30<\/a><\/strong>
31<\/a>
32<\/a>
33<\/a>
34<\/a>
35<\/a>
36<\/a>
37<\/a><\/pre><\/td>\n  
class<\/span> <\/span>Gcd<\/span>
<\/span>  <\/span>#GCD(m,n)<\/span>
<\/span>  <\/span># Step 1 : Divide m/n and r is the remainder 0<=r<=n<\/span>
<\/span>  <\/span># Step 2   if r = 0 then n is the GCD of m,n<\/span>
<\/span>  <\/span># r !=0 then m =n and n =r go to step 1<\/span>
<\/span>  <\/span># m can be less than n to make the algorithm faster make sure m is greater than n<\/span>
<\/span>  <\/span>#<\/span>
<\/span>  <\/span># e.g   2322, 654<\/span>
<\/span>  <\/span>#       1071, 1029<\/span>
<\/span>  <\/span>#       1769,551<\/span>
<\/span>  <\/span>#       2166,6099<\/span>
<\/span>  <\/span>#       163231, 135749<\/span>
<\/span>  <\/span>attr_accessor<\/span> <\/span>:m<\/span>,<\/span> <\/span>:n<\/span>
<\/span>
<\/span>  <\/span>def<\/span> <\/span>initialize<\/span>(<\/span>m<\/span>,<\/span> <\/span>n<\/span>)<\/span>
<\/span>    <\/span>m<\/span>,<\/span> <\/span>n<\/span> <\/span>=<\/span> <\/span>m<\/span>.<\/span>to_i<\/span>,<\/span> <\/span>n<\/span>.<\/span>to_i<\/span>
<\/span>    <\/span>if<\/span> <\/span>(<\/span>m<\/span> <\/span>><\/span> <\/span>n<\/span>)<\/span>
<\/span>      <\/span>@m<\/span>,<\/span> <\/span>@n<\/span> <\/span>=<\/span> <\/span>m<\/span>,<\/span> <\/span>n<\/span>
<\/span>    <\/span>else<\/span>
<\/span>      <\/span>@m<\/span>,<\/span> <\/span>@n<\/span> <\/span>=<\/span> <\/span>n<\/span>,<\/span> <\/span>m<\/span>
<\/span>    <\/span>end<\/span>
<\/span>    <\/span>compute<\/span>(<\/span>m<\/span>,<\/span> <\/span>n<\/span>)<\/span>
<\/span>  <\/span>end<\/span>
<\/span>
<\/span>  <\/span>def<\/span> <\/span>compute<\/span>(<\/span>m<\/span>,<\/span> <\/span>n<\/span>)<\/span>
<\/span>    <\/span>r<\/span> <\/span>=<\/span> <\/span>nil<\/span> <\/span>#<\/span>
<\/span>    <\/span>p<\/span> <\/span>Time<\/span>.<\/span>now<\/span>
<\/span>    <\/span>while<\/span> <\/span>(<\/span>r<\/span> <\/span>=<\/span> <\/span>m<\/span> <\/span>%<\/span> <\/span>n<\/span>)<\/span>!=<\/span> <\/span>0<\/span>
<\/span>      <\/span>m<\/span> <\/span>=<\/span> <\/span>n<\/span>
<\/span>      <\/span>n<\/span> <\/span>=<\/span> <\/span>r<\/span>
<\/span>    <\/span>end<\/span>
<\/span>    <\/span>p<\/span> <\/span>"<\/span>The GCD of <\/span>#{<\/span>@m<\/span>}<\/span><\/span>, <\/span>#{<\/span>@n<\/span>}<\/span><\/span> is <\/span>#{<\/span>n<\/span>}<\/span><\/span>"<\/span><\/span>
<\/span>    <\/span>p<\/span> <\/span>Time<\/span>.<\/span>now<\/span>
<\/span>  <\/span>end<\/span>
<\/span>end<\/span>
<\/span>
<\/span>
<\/span><\/pre><\/td>\n<\/tr><\/table>\n\n");