$("#ray_6234").html("
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");
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");