Thread: Brute Force

Hi, I'm new to Algorithm And Analysis, I just started and found some problem, that is Brute Force,

In the Example,

GCD(m,n)

Brute Force - Consecutive Integer Checking
Step 1 - Assign the value of min {m,n} to t

Step 2 - Divide m by t. If the remainder of this division is 0, go Step 3, otherwise Step 4

Step 3 - Divide n by t. If the remainder of this division is 0, return the value of t as the answer and stop. Otherwise go Step 4

Step 4 - Decrease the value of t by 1. Go to Step 2

My Question is: I completely don't understand this clearly, Can someone help explain to me? Thanks for the help...

Thanks for replying!

Lets use this example GCD(60,24)

Step 1 - What is min {m,n} ? after get the value assign to t, what is "t" ? Remainder?

Originally Posted by 123sample

Thanks for replying!

Lets use this example GCD(60,24)

Step 1 - What is min {m,n} ? after get the value assign to t, what is "t" ? Remainder?

You're looking for the greatest common denominator, and 24 is the minimum of the set with {60, 24}.

Clearly, the gcd can not be larger than 24, so that's your starting point.

With C, if you want to check just the remainder first, I might use the modulus operator: %.

So m=60, n=24, and t=24, we want to know if m%t==0. And we need to make that check in a loop:

Code:

while (t > 1) {
  if(m % t == 0) {  //got one denominator
    //repeat with n 
        //if t is common to m and n, that's the gcd - break here
  }
  decrement t;
}

//print out the gcd you found