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)

[code][/code]tagged by Salem

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.

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;

}

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.

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]

Thanks for your help with this..

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.

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.

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.