Member Avatar for plike922

I am trying to create a program that finds the GCD of two numbers using the brute force...
So far i have this but my problem (I hope) is that i cant get the value of g into int main()
Here is my program. Any suggestions?

#include <cstdio>
#include "simpio.h"
#include "strlib.h"

int GCD(int x, int y)
{
	int g;

	g = x;
	while (x % g != 0 || y % g != 0)
	{
		g--;
		}
	return(g);
}

int main()
{
  int n1,n2;

  printf("1st number = ");
  scanf("%d",&n1);

  printf("2nd number = ");
  scanf("%d",&n2);

  printf("The GCD of %d and %d is %d",n1,n2,GCD(g));

  return 0;
  system("pause");
}
  • 4 Contributors
  • 3 Replies
  • 191 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by Prabakar

Dani AI

Generated

The immediate bug is simple: main tried to call GCD with a variable g that only exists inside the function. Pass the two input values to the function and capture its return (as and already pointed out). Also note that system("pause") after return is unreachable; either put it before return or remove it. Replace nonstandard includes (simpio.h, strlib.h) with the standard headers you actually need (stdio.h, stdlib.h) and compile with warnings enabled (for example -Wall -Wextra) so the compiler will point out these mistakes.

If you want to keep the brute-force approach but make it robust and faster, start the search at the smaller absolute value and handle zeros/negatives:

int gcd_bruteforce(int a, int b)
{
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    if (a == 0) return b;
    if (b == 0) return a;
    int g = (a < b) ? a : b;
    while (g > 0) {
        if (a % g == 0 && b % g == 0) return g;
        --g;
    }
    return 1;
}

For real code prefer the Euclidean algorithm — much faster and simpler for large inputs:

int gcd_euclid(int a, int b)
{
    if (a < 0) a = -a;
    if (b < 0) b = -b;
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

Notes: decide how to treat gcd(0,0) (mathematically undefined), use a wider integer type (long long) for very large values, and test edge cases (zero, negatives, equal numbers). As suggested, starting from the smaller number speeds brute force, but for practical purposes use Euclid's method.

Recommended Answers

All 3 Replies

Member Avatar for Major Major 
printf("The GCD of %d and %d is %d",n1,n2,GCD(g));

Try this instead

printf("The GCD of %d and %d is %d",n1,n2,GCD(n1,n2));
Member Avatar for Aia

In main:

int result;

result = GCD( n1, n2);
printf("result = %d\n", result);
Member Avatar for Prabakar

>> g = x ;
g has to be least of the 2 numbers rather than simply x for the code to be faster.
Why brute force?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.