GCD the Brute-Force Way

[DzyTC542]

Ok. I already wrote a program to compute the GCD of 2 numbers using Euclid's algorithm, but now I have to write another program to compute the GCD of 2 numbers the force way. Here's what I have so far, but the output is _. All help appreciated. By the way, we are writing in C.

/* 
* File name: GCD1.c
* This program computes and displays the greatest common divisor of two numbers.
*/

#include <stdio.h>
#include "genlib.h"
#include "simpio.h"

main()
 {
	int a, b, c, GCD;
	printf (" Enter a number: \n");
	a = GetInteger();
	printf (" Enter a second number: \n");
	b = GetInteger ();
	while (a>b)
	if (b%a == 0) GCD = b;
	else 
	while (b%a != 1)
		{
			b--;
			c=b%a;
			if (c==0) GCD = b;
		}
 printf (" The GCD of %d and %d is %d", a, b, GCD);	
 getchar();
}

[tipaye]

Hmm

if (a <= b), the rest of your code (lines 18-25 will never run and uninitialised GCD will be some random value

if (a > b), then b%a == b, and you'll skip to line 20. From here, it runs away from you:

you're stuck in your second while loop until b == 1, at which point you'll wind up back at 17, and you'll forever be stuck between 17 and 18.

If you ever wonder why people get so passionate about code formatting, indentation and brace placement, this is why. I've reformatted the code, and it should be clearer why it's going wrong.

P.S. With this sort of problem it's better you give examples of bothe input and related output, and don't leave us guessing about whether GetInteger() is actually messing things up or not...

/*
 * File name: GCD1.c
 * This program computes and displays the greatest common divisor of two numbers.
 */

#include <stdio.h>
#include "genlib.h"
#include "simpio.h"

main()
{
    int a, b, c, GCD;
    printf (" Enter a number: \n");
    a = GetInteger();
    printf (" Enter a second number: \n");
    b = GetInteger ();
    while (a>b)
    {
        if (b%a == 0)
        {
            GCD = b;
        }
        else
        {
            while (b%a != 1)
            {
                b--;
                c=b%a;
                if (c==0)
                {
                    GCD = b;
                }
            }
        }
    }

    printf (" The GCD of %d and %d is %d", a, b, GCD);
    getchar();
}

I think you can clearly see that if (a <= b) you'll never into that first while look, and if (a > b) you'll never get out of it.

[DzyTC542]

Ok. I tried a>=b, but when my input is 10, 5, the output is 70.

[tipaye]

You still have the same problem.
You start with b < a and then you keep decrementing b until a >= b, you can see this is already true and will continue to be so, because after b%a == 1, you never change anything and so will never exit your while (a>= b) loop.

It is not so much the conditions as the logic that needs re-working.

Also, if you didn't change anything else in the program, there's no way you got any output from the input you specified. If you did change stuff, then you should say so, and show your changes.

I saw someone else do a GCD on this site earlier today, don't know if it's what you're after, but it may help:

int GCD(int a, int b)
{
    int r = a%b;
    if (r!=0)
    {
        return GCD(b, r);
    }
    return b;
}

added reminder: it's up to you to make the input conform, so you determine which one os greater beforehand

[DzyTC542]

Thanks for your help, I got it! yay! Now I need help on another program. I need to read a list of strings until the word "end" appears and then print the longest string/word. Here's what I've got so far, any help is appreciated.

/* this program reads a list of strings until the word end appears and returns the longest string that was included in the input list.*/

#include <stdio.h>
#include "genlib.h"
#include "simpio.h"
#include "strlib.h"

int main()
{
	string string, max,s2;
	int sLength,slength;
	printf ("Signal end of output with the word end\n");
	printf ("Enter next string");
	string= GetLine();
	max=string;
	s2=string;
	slength=sLength;
	while (!(StringEqual(string, "end"))) 
  	{
  		printf("\nEnter your next string: ");
  		string = GetLine();
  		sLength = StringLength(string);
  		if (slength>sLength)
  		max=s2;
  		else if (sLength>slength)
  		max=string;
		printf (" The longest string is: %s", max);		
	}
		getchar();
	}

My output is always the first string, regardless of everything else. For example, with the inputs 'the' and 'longest', my output is 'the'. Do you know what is the problem?

[tipaye]

Don't know what library you're using or the contents of the header files, so I'll go ahead and guess.

in line 10 I see an impossibility "string string" - is string a type or a variable?

The use of s2 is unnecessary and only confuses things, and deciding the longest string in the while loop doesn't make things any clearer.

Generally, the choice of variable names (slength, sLength, s2) is ill-advised and will trip you up sooner or later. Also, you don't seem to use the length variables beyond comparing them, so I got rid of them.

The name "GetLine()" suggests you're reading a whole line not just a word, and I wonder if you want to be looking for the wrod "end" as a single line all by itself, or scanning each input line for occurences of "end"

I've tried to "head-compile" it but I can't be sure there aren't mistakes or typos, so take this with a pinch of salt...

* this program reads a list of strings until the word end appears and returns the longest string that was included in the input list.*/

#include <stdio.h>
#include "genlib.h"
#include "simpio.h"
#include "strlib.h"

int main()
{
	string currStr, maxStr;
	printf ("Signal end of output with the word end\n");
	printf ("Enter next string\n");
	currStr = GetLine();
	maxStr = currStr;
	while (!(StringEqual(currStr, "end"))) 
  	{
  		printf("Enter your next string: ");
  		currStr = GetLine();
  		if (StringLength(currStr) > StringLength(maxStr ))
		{
			maxStr = currStr;
		}
	}
	
	printf ("The longest string is: %s\n", maxStr);		
	getchar();
}

[IWishIKnew]

It's not "the brute force way", it's using brute force.

Basically, you will try every concievable combination (O(n!)) possible until you find all of them.

I imagine you would find all the factors of each number, sort their factors from greatest to least, and then iterate over them.

[ne555]

> you will try every concievable combination (O(n!)) possible
¿combinations of what? ¿what are you counting? ¿what's `n'?
If you test with more than min(a,b) numbers you are doing something very wrong.

> I imagine you would find all the factors of each number, sort their factors from greatest to least, and then iterate over them.
unnecessary complex.

[IWishIKnew]

ne555:

Your not counting... you're comparing two numbers.

as it's 10pm for me, I am not going to explain it to you in this post... why don't you try finding all the common factors of two numbers on paper a few times and get the algorithm down in your head. You might understand after that.

[helios]

IWishIKnew, it seems, is still under the misapprehension that s/he understands anything.

why don't you try finding all the common factors of two numbers on paper a few times and get the algorithm down in your head.

You don't need to do factorization to find the GCD, even if you do it by brute force.

l_n = sorted_divisors_of(first_number); //O(n)
l_m = sorted_divisors_of(second_number); //O(n)
l = intersect(l_n, l_m); //O(n)
gcd = max(l); //O(n) 

You can but why would you?

[IWishIKnew]

of, greatest common denominator... I mesread it as greatest common factor.

Sorry for the confusion. Disregard my previous post.

[helios]

There's no such thing as a greatest common factor. Now, a least common multiple...