Highest Common factor
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++; } }
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now