Highest Common factor

Abdul Samad · February 14, 2017

I was making a program that could give me HCF of two numbers
i din't know what has happened wrong but it is given strange answers
here is the code

#include <iostream>

using namespace std;

int main(void)
{
int n1; int n2; int f1[100]; int f2[100]; int c1=0; int c2=0; int com[100];

cin >> n1;
cin >> n2;
int e = 0;
for(int a=1;a<n1;a++){
if (n1%a==a){
f1[c1]=a;
c1++;
}
}
for(int b=1;b<n2;b++){
if(b%n2==0){
f2[c2]=b;
c2++;
}
}

for(int c=0;c<c1;c++){
for(int d=0;d<c2;d++){
if(f1[c1]==f2[d]){
com[e]=f1[c2];
e++;
}
}
}

int heighest=com[0];
for(int f=1;f<e;f++){
if(com[f]>heighest){
heighest=com[f];
}
}

cout << "heighest common factor is:" << endl;
cout << heighest;
return 0;
}

Mira Yurizaki · February 14, 2017

Nit picky things:

Please use the code tags next time (it's the < > icon next to the eye and double quote icons)
The proper term is Greatest Common Factor/Divisor (this is me being pedantic, so don't mind me here)

Anywho.

The first is that the algorithm is inefficient. You should stop at the halfway point of each number because after that, you're repeating work (e.g., the factors of 36 are 2, 3, 4, 6, 9, and 13. You can stop at 13 because you can figure out the rest using the other numbers at the same time you found them).

i.e., for example in the first loop:

for(a = 1;a < (n1/2);a++){
  if ( n1 % a == 0){
    f1[c1++] = a;
    f1[c1++] = n1/a;
  }
}

Second, since this is finding the highest number, when you go compare the two numbers' divisors, you should work backwards ~~and you should stop when the value being compared is less than the value comparing to~~. I have a feeling the first thing it hits will be the GCD, but I haven't run this to verify. So you may not even need to continue looping once you've found the value.

EDIT: I can't think of a way to verify the divisor value thing yet, so here's this.

for(int c = a ; c > 0; c--){
  for(int d = b; d > 0; d--){
    if(f1[c] == f2[d]){
      com[e]=f1[c];
      e++;
    }
  }
}

Although writing that allowed me to find something weird and may be the root of your problem

for(int c=0;c<c1;c++){
  for(int d=0;d<c2;d++){
    if(f1[c1]==f2[d]){ 
      // You should be using c instead of c1, as c1 does not change
      // and so you're comparing f2 to the same value all the time
      com[e]=f1[c2];
      // Why use c2 when you're indexing using d?
      e++;
    }
  }
}

EDIT: I also found another weird spot:

for(int a=1;a<n1;a++){
  if (n1%a==a){ // This has issues because, for example, 20 % 5 = 0. It does not equal 5. 5 is a divisor of 20.
    f1[c1]=a;
    c1++;
  }
}

Edited February 14, 2017 by M.Yurizaki

Mira Yurizaki · February 14, 2017

Of course, if you want, you can also use another algorithm like Euclid's or the Binary method.

I just wanted to fix what was there first

Nineshadow · February 14, 2017

Learn Euclid's algorithm: https://en.wikipedia.org/wiki/Euclidean_algorithm.

def gcd(a, b):
    while a ≠ b :
        if a > b:
           a = a − b; 
        else:
           b = b − a; 
    return a;

And the recursive version

def gcd(a, b):
    if b = 0:
       return a; 
    else:
       return gcd(b, a mod b);

Ps: gcd is already in STL, although in an experimental fashion.

Mira Yurizaki · February 14, 2017

3 hours ago, Nineshadow said:
Learn Euclid's algorithm: https://en.wikipedia.org/wiki/Euclidean_algorithm.
def gcd(a, b):
    while a ≠ b :
        if a > b:
           a = a − b; 
        else:
           b = b − a; 
    return a;
And the recursive version
def gcd(a, b):
    if b = 0:
       return a; 
    else:
       return gcd(b, a mod b);
Ps: gcd is already in STL, although in an experimental fashion.

I have a feeling this is homework.

But eh, it's nice to exercise the brain