Thread: C program for finding highest common factor!!

Hi to all,

I need a C program that finds the Highest Common Factor of numbers entered by a user. Does anyone have such a program or can provide with a link that at least explain the logic of such a program.

Warm regards,
Visham

http://en.wikipedia.org/wiki/Euclidean_algorithm

To find the GCD of a set of numbers, find the GCD of the first two, then the GCD of that with the third, then the GCD of that with the fourth, etc., i.e.

GCD(a, b, c, d) == GCD(GCD(GCD(a, b), c), d)

So, let's say someone enters the two numbers:

42 and 21. The greatest common denominator is 7.
Enter
27 and 81, and the greatest common denominator is 27. (27 * 3 = 81).

How do we come up with that? Well, there's really nothing other than dividing both numbers with some numbers to see if it can be divided evenly with that number. The largest number BOTH numbers can be divided by is the "highest common factor".

--
Mats

But the Euclidean algorithm doesn't require factoring, and is both much more efficient and easier to implement than anything involving factoring. The pseudocode for the iterative version of the algorithm in the above link can be directly turned into a 5 or 6 line C function.

Hi to all,

First of all, many thx to robatino, elton_fan, matsp for their help with the GCD function logic.

I have written a program that uses the weighted round-robin (WRR) algorithm. It should print the name of the server that is selected based on the weights assigned to each server. But it is not working as required.

On the LVS website, it said the following about WRR algorithm's output:

For example, the real servers, A, B and C, have the weights, 4, 3, 2 respectively, a scheduling sequence will be AABABCABC in a scheduling period (mod sum(Wi)).

With my program I dont get the output as quoted in the example above. I would be very grateful if someone can pls check it for me and indicate what is wrong..

Warm regards,
Visham

My program is as follows:

Code:

/* The pseudo code of weighted round-robin scheduling is as follows:
 *
 * Supposing that there is a server set S = {S0, S1,.., Sn-1};
 * W(Si) indicates the weight of Si;
 * i indicates the server selected last time, and i is initialized with -1;
 * cw is the current weight in scheduling, and cw is initialized with zero;
 * max(S) is the maximum weight of all the servers in S;
 * gcd(S) is the greatest common divisor of all server weights in S;
 *
 * while (true) {
 *     i = (i + 1) mod n;
 *     if (i == 0) {
 *         cw = cw - gcd(S);
 *         if (cw <= 0) {
 *             cw = max(S);
 *             if (cw == 0)
 *             return NULL;
 *         }
 *     }
 *     if (W(Si) >= cw)
 *         return Si;
 * }
 *
 * For example, the real servers, A, B and C, have the weights, 4, 3, 2 respectively, a scheduling sequence will be AABABCABC in a scheduling period
 * (mod sum(Wi)).
 *
 *########### The Euclidean Algorithm pseudocode ############
 * Using recursion
 * Using recursion, the algorithm can be expressed naturally:
 *	  function gcd(a, b)
 *	      if b = 0 return a
 *	      else return gcd(b, a mod b)
 *
 * Using iteration
 * This is more efficient with compilers that don't optimize tail recursion:
 *	  function gcd(a, b)
 *	     while b != 0
 *	         t := b
 *	         b := a mod b
 *	         a := t
 *	     return a
 *
 *##########################################################
 *
 */

#include <stdio.h>
#include <conio.h>
#include <math.h>

int max_calculator(int weight[], int asize);
int hcf_calculator(int weight[], int asize);


main()
{
	char * slist[10]; /* Used to store the server names entered */
	int weight[10]; /* array for storing the weight associated with each server */
	int wno; /* number of servers (or weights) */
	int n; /* a counter */
	/* variables used in the WRR algo as defined at the top */
	int i= -1, cw= 0, v, hcf, maxw; /* hcf and maxw are used to store the hcf and the max value of the weights specified */

	clrscr();
	printf("\nEnter the number of servers:\n");
	scanf("&#37;d",&wno);

	memset(weight, '\0',sizeof(weight));

	printf("\nEnter the %d servers names:\n",wno);

    /* for loop for storing the name of servers. Just type a letter (say Albert) and press enter. Type 4 times to enter 4 different server names */
	for(n=0;n<wno;n++) {
		slist[n] = (char *) malloc(10 * sizeof(char));
		memset(slist[n], '\0',sizeof(slist[n]));
		scanf("%s",slist[n]);
	}

	/* Prints the contents of each server name entered..For checking purposes */
	for(n=0;n<wno;n++) {
		printf("\nServer name %d  = %s",n, slist[n]);
	}

	printf("\n\nEnter the weights:\n");
	for(n=0;n<wno;n++) {
		scanf("%d",&weight[n]);
	}

	hcf = hcf_calculator(weight, wno);
	maxw = max_calculator(weight, wno);

	/* run the WRR algo ten times to see what server is picked, whether it's A, B, C or D, and in what order based on the weights assigned */
	for (v=0;v<10;v++) {

		while (1) {
			i = (i + 1) % wno;
			/* printf("\nvalue of i = %d",i); */ /* for checking the value of i */
			if (i == 0) {
				cw = cw - hcf;
				if (cw <= 0) {
					cw = maxw;
					if (cw == 0)
						return NULL;
				}
			}
			if (weight[i] >= cw){
				/* printf("\nvalue of weight[i] = %d",weight[i]); */ /* for checking the value of weight[i] */
				printf("%s",slist[i]);
				break;
			}
		}
		printf("\n");
	}
 getch();
	return 0;

}

/* Function to find maximum among the weight values entered */
int max_calculator(int weight[], int asize)
{
	int maxval= 0, i= 0;

	for(i=0;i<asize;i++) {
		if(i == 0)
			maxval = weight[i];

		else
			if(weight[i] > maxval)
				maxval = weight[i];
	}
	printf("\n\nmax weight = %d\n\n",maxval);
	return maxval;
}

/* Function to find HCF of the weight values entered */
int hcf_calculator(int weight[], int asize)
{
	int i, a, t;

	a = weight[0];

	for(i=0;i<(asize-1);i++) {
		/* function gcd(a, b) */
		t = 0;
		while(weight[i+1] != 0) {
			t = weight[i+1];
			weight[i+1] = a % weight[i+1];
			a = t;
		}
	}
	printf("\n\nHCF = %d\n\n",a);
    return a;
}

Code:

/* The pseudo code of weighted round-robin scheduling is as follows:
 *
 * Supposing that there is a server set S = {S0, S1,.., Sn-1};
[ ... ]
 * gcd(S) is the greatest common divisor of all server weights in S;

The Euclidean algorithm computes the GCD of two numbers, not a whole set of numbers.

Most efficient would be a method that considers the entire set at once I believe. You could run the Euclidean algorithm on every possible subset of S, but that might take a while and sounds like more trouble than its worth, because you'd have to keep track of your answers.

Some sets, like 4, 3, 2, also only share a factor of one.

If one of the two numbers is small, the Euclidean algorithm finishes faster (although it's pretty fast regardless), and if one of the numbers is 1, then the result must be 1, so if one is taking the GCD of a large set of numbers, one could check after each result if it equals 1 and if so, quit immediately.

Originally Posted by iMalc

Wrong, it would be 21 because 42 is exactly double 21.Answers like this really scare me.

Of course it is. I think that I meant to have 49 instead of 42 in which case 7 would have been the correct answer...

The Euclidean GCD algorithm is far more efficient that the naieve approach you describe. Suggesting that the naieve brute force approach is the only way, shows a real lack of formal computer science education.

Not entirely without education, just a long time ago, that combined with my eagerness to answer - ever so sorry. I've been known to type first and think later, which sometimes leads to bad results... :-(

--
Mats