C program for finding highest common factor!!

This is a discussion on C program for finding highest common factor!! within the C Programming forums, part of the General Programming Boards category; Hi to all, I need a C program that finds the Highest Common Factor of numbers entered by a user. ...

  1. #1
    Registered User
    Join Date
    Sep 2005
    Posts
    22

    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

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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)

  4. #4
    Registered User
    Join Date
    Jan 2007
    Posts
    72
    i think you have to go over discret mathematics to know a lot about the logic of these mathematical structures
    proud to be from aui www.aui.ma and also a great elton john's fan

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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.

  7. #7
    Registered User
    Join Date
    Sep 2005
    Posts
    22
    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;
    }

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,525
    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.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by matsp View Post
    42 and 21. The greatest common denominator is 7.
    Wrong, it would be 21 because 42 is exactly double 21.
    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".
    Answers like this really scare me.
    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.
    Last edited by iMalc; 08-02-2007 at 01:24 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Quote Originally Posted by robatino View Post
    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.
    Which perhaps leads onto the idea of sorting the numbers ascending first...
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by iMalc View Post
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. factor program
    By krazykrisi in forum C++ Programming
    Replies: 5
    Last Post: 09-27-2006, 06:39 AM
  2. Can someome help me with a program please?
    By WinterInChicago in forum C++ Programming
    Replies: 3
    Last Post: 09-21-2006, 10:58 PM
  3. I need some help with my program please.
    By agentxx04 in forum C Programming
    Replies: 9
    Last Post: 09-26-2004, 07:51 AM
  4. My program, anyhelp
    By @licomb in forum C Programming
    Replies: 14
    Last Post: 08-14-2001, 10:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21