Solver Find the GCD (or GCF) of two numbers using Euclid's Algorithm

Algebra -> Algebra -> Divisibility and Prime Numbers -> Solver Find the GCD (or GCF) of two numbers using Euclid's Algorithm Log On

Ad: Algebra Solved!™: algebra software solves algebra homework problems with step-by-step help!
Ad: Algebrator™ solves your algebra problems and provides step-by-step explanations!

Algebra: Divisibility and Prime Numbers

Solvers

Lessons

Problems, free tutors

Quiz

In Depth

Source code of 'Find the GCD (or GCF) of two numbers using Euclid's Algorithm'

This Solver (Find the GCD (or GCF) of two numbers using Euclid's Algorithm) was created by by jim_thompson5910(13794)

: View Source, Show, Put on YOUR site
About jim_thompson5910:

==section input

This solver finds the GCD (greatest common divisor) or GCF (greatest common factor) of two numbers (two positive whole numbers) by use of <a href="http://en.wikipedia.org/wiki/Euclidean_algorithm">Euclid's Algorithm</a>

Enter two numbers: First Number: *[input num1=24] and  Second Number: *[input num2=36]

Note: if you need to find the GCD of more than two numbers, chain the solvers.

For instance, if you need the GCD for 6, 8, and 10, then find the GCD of 6 and 8 (which is 2). Now find the GCD of 2 and 10 (which is 2). So the GCD of 6, 8, and 10 is 2. This will work for any number of numbers.

==section solution

perl

if(($num1=~m/\D/)||($num2=~m/\D/))
{
 print " Please enter two positive whole numbers ";
 return;
}

if(($num1==0)||($num2==0))
{
 print " Please enter two non-zero numbers ";
 return;
}

my $new_num1,$new_num1,$remainder;
$new_num1=$num1;
$new_num2=$num2;

print "Let {{{a=$num1}}} and {{{b=$num2}}}. Also, let's introduce the variable \"r\" for the remainder ";

$table.="<table border=\"1\"><th>a</th><th>b</th><th>r</th>";

$table.="<tr><td>$new_num1</td><td>$new_num2</td><td></td></tr>";

my $i=0;

while($new_num2!=0)
{
  $i++;
  my $quo=$new_num1/$new_num2;
  $quo=~s/\.\d+//;
  $remainder=$new_num1%$new_num2;

print " Round $i: ";

print " Let's evaluate {{{a/b}}}. It turns out that {{{a/b=$new_num1/$new_num2}}} = $quo remainder $remainder. What we're are interested in is the remainder. So let {{{r=$remainder}}}. Now assign the value of \"b\" to \"a\" and the value of \"r\" to \"b\". ";

#print " So now {{{a=$new_num1}}} , {{{b=$new_num2}}} and {{{r=$remainder}}} ";

#We'll use the <a href=\"\">modulo</a> (or mod) function. ";
 #print " So this means that r = a mod b = $num1 mod $num2";

$new_num1=$new_num2;
 $new_num2=$remainder;
 $table.="<tr><td>$new_num1</td><td>$new_num2</td><td>$remainder</td></tr>";

#print " = $remainder This value is the remainder. Now assign the value of \"b\" to \"a\" and assign the value of the remainder \"r\" to \"b\" ";

print " So now {{{a=$new_num1}}}, {{{b=$new_num2}}}, and {{{r=$remainder}}} ";

#print " num1=$num1, num2=$num2, rem=$remainder ";

if($new_num2!=0)
 {
 print " Now we must ask ourselves: \"Does b=0?\". Since b=$new_num2 (which is NOT zero), we must start all over and keep going until \"b\" equals zero. ";
 print " ------------------------------------- ";
 }

}

print " Since the value of b is now zero, we can stop the process. ";

$table.="</table>";

print " So this is what we've done so far (note: each row is a separate round): ";

print " $table ";

print " Now the value of \"a\" in the last row is the GCD of the numbers \"a\" and \"b\" ";

print " So this means that GCD($num1,$num2)=$new_num1. In other words, the GCD (or GCF) of $num1 and $num2 is $new_num1 ";

if($new_num1==1)
{
 print " Note: since the GCD is 1, this means that the numbers $num1 and $num2 are relatively prime. ";
}

==section output

==section check