Thread: HCF problem - C++ basics..

  1. #1
    Registered User
    Join Date
    May 2002
    Posts
    7

    Question HCF problem - C++ basics..

    I'm just getting my feet wet with C++ and could do with some pointers (no pun meant) with the logic of programming..
    I'm trying to write a very basic and small program to work out the Higest Common Factor of 2 int numbers, as entered by the user.
    Please don't laugh, but here is my effort, which does not work.

    I'm looking for your comments on where I've gone wrong...
    Code:
    #include <iostream.h>
    #include <iomanip.h>
    
    int main()
    {
    	int num1, num2, factor=0, factor1, factor2;
    
    	cout<<"Enter the first number ";
    	cin>>num1;
    	cout<<"Enter the second number ";
    	cin>>num2;
    
    	do
    	{
    		factor1=num1%factor;
    		factor2=num2%factor;
    		factor++;
    		
    	}	
    	while(num1%factor!=0 && num2%factor!=0);
    	
    
    
    	cout<<"Factor is "<<factor;
    
    	return 0;
    
    }
    Sorry if this is a muppet question.

    Hope you can 'show me the light'..

    Cheers fellas (and any ladies, to be PC)

    &#91;code]&#91;/code]tagged by Salem

  2. #2
    Registered User GreenCherry's Avatar
    Join Date
    Mar 2002
    Posts
    65
    I really dont see where your program is going. Factor will always be two at the end, unless both numbers are evens, then it will be 3.
    I have a rabbit in my pants! Please be happy for me.

  3. #3
    Me want cookie! Monster's Avatar
    Join Date
    Dec 2001
    Posts
    680
    HIGHEST COMMON FACTOR

    if factor is 0 you will get a divide by zero error

    make factor the smallest value of num1 and num2 and count
    back to 1:

    Code:
    int main()
    {
       int num1, num2, factor;
    
       cout<<"Enter the first number ";
       cin>>num1;
       cout<<"Enter the second number ";
       cin>>num2;
    
       if(num1 <= 0 || num2 <= 0)
          return -1;
    
       factor = (num1 < num2 ? num1 : num2);
    
       while(num1%factor || num2%factor)
          factor--;
    
       cout<<"Factor is "<<factor;
    
       return 0;
    
    }

  4. #4
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    factor1=num1%factor;
    Whats factor equal to first time thru the loop. Division by zero is not allowed remember.

    EUCLIDS ALGO

    Given 2 positive integers a and b
    find max (assume a>=b for the purpose of this algo)
    loop: divide a by b
    remainder=r
    if r=0 answer is b
    a=b
    b=r
    goto loop

    now translate that into code. DO NOT USE A GOTO but instead a while loop.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  5. #5
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    You have the right logic, but your mistake is that by starting at zero and working up you in the end find the LOWEST factor, since the second it finds any factor it ends the loop. Even then it doesn't work because you set factor equal to zero instead of two - and although I'm not sure if anything % zero is zero (I'm pretty sure it is though) anything % one IS zero, so the loop will always stop immediately.

    If you want to find the highest factor the way you have going on now, start factor at the lowest of num1 and num2, and work backwards using a while loop, not a do/while loop.

    [edit] LOL wow, all three of us writing at the same time [/edit]

  6. #6
    Registered User
    Join Date
    May 2002
    Posts
    7
    Thanks for your help with this..

  7. #7
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    Also, you're missing a subtle optimization.

    You only have to check numbers from one extreme to the square root of the number -- not from the extreme to the opposite extreme

    This is because once you find a factor greater than the square root you know it has a corresponding number less than the square root that when multiplied together with your found factor equals your original number! The same goes for the opposite -- if there is a factor below the square root there is a corresponding factor above it. So there is no point in checking on both sides of the square root explicitly.
    Last edited by Polymorphic OOP; 12-04-2002 at 05:12 AM.

  8. #8
    Registered User
    Join Date
    May 2002
    Posts
    7

    Just a quick query on the logic.

    Okay, I think I've got the idea, however I'm a bit stuck with the following bit of code logic:

    while(num1%factor || num2%factor)

    I understand that this is testing the remainder of num1/factor and as long as the result is non zero, the loop continues - however, working through the logic, if the values 12 and 18 (for example) are entered and 18 is set as 'factor', when this is tested against itself the answer will be 1, as 18/18 = 1 remainder 0 - surley this should stop the loop ???? Why dosen't it??

    Thanks again

    Frustrated form the UK.

  9. #9
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    The logical or operator will continue to return true until both sides of the expression evaluate to zero. Then and only then does the loop end.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  2. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  3. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  4. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  5. beginner problem
    By The_Nymph in forum C Programming
    Replies: 4
    Last Post: 03-05-2002, 05:46 PM