My GCF/GCD program is returning an extra number

Question

I want my program only to return the greatest common factor but instead it returns a bunch of random factors and finally the answer.

I tried using a a website that shows the steps of your code.

list_fac = []
def gcf(num1, num2):
    x = max(num1, num2)
    for i in range(2,x + 1):
        if x % i == 0:
            list_fac.append(i)


            y = min(num1, num2)
            for t in list_fac:
                if y % t != 0:
                    list_fac.remove(t)
                    print(max(list_fac))

I want it to return a single answer but it returns some factors then an answer.

gcf(10,20)

expected:

actual:

2
10

Why not use Euclid's algorithm? And you've computed the answer as a list, just take the last element and you're done, no? Or don't bother creating a list, just save the latest factor you've found and you're done. Best yet, use `from fractions import gcd` and `gcd(10, 20)`. See [this](https://stackoverflow.com/a/11175154/6243352). — ggorlen, Aug 07 '19 at 23:14
I tried printing list_fac[-1] at the very end, but still it returned 2 and then 10, i think it is in some sort of loop. — SSJGOLEM, Aug 07 '19 at 23:17
Works fine for me. https://repl.it/repls/EmotionalSubstantialMolecule. The Euclid algorithm is a three-liner though and far more efficient, or just use the builtin. Recommend. — ggorlen, Aug 07 '19 at 23:20
I figured it out, my program loops, instead waiting to file through all the factors, as soon as it finds a factor that is a factor of both numbers, it prints. I just have to get the program to loop until it process all factors. Thanks ggorlen — SSJGOLEM, Aug 07 '19 at 23:27

ggorlen · Answer 1 · 2019-08-08T00:22:54.560

This code is essentially correct. You have your answer at list_fac[-1], if it isn't 1. You can fix this by iterating from range(1, x + 1):

def gcf(num1, num2):
    list_fac = []
    x = max(num1, num2)
    y = min(num1, num2)

    for i in range(1, x + 1):
        if x % i == 0:
            list_fac.append(i)

            for t in list_fac:
                if y % t != 0:
                    list_fac.remove(t)

    return list_fac[-1] if list_fac else 0

if __name__ == "__main__":
    print(gcf(10, 20)) # => 10

However, the code is inefficient and difficult to follow. For example, the inner loop does not need to iterate twice over list_fac (list.remove() traverses the whole list).

You only need consider whether the last element added is also divisible by zero. Nor is it necessary to keep the entire list in memory since we only care about the last thing added (largest element so far):

def gcf(num1, num2):
    greatest = 0
    x = max(num1, num2)
    y = min(num1, num2)

    for i in range(1, x + 1):
        if x % i == 0 and y % i == 0:
            greatest = i

    return greatest

I recommend using the Euclidean Algorithm as follows (see the linked article or this thread for details on why the complexity is an improvement on linear):

def gcd(a, b):
    while b:
        a, b = b, a % b

    return a

Even easier, the folks at Python have a builtin:

Python 3.7.2 (default, Mar 11 2019, 20:44:31)
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> from math import gcd
>>> gcd(10, 20)
10

Python 3.4.3 (v3.4.3:9b73f1c3e601, Feb 24 2015, 22:43:06) [MSC v.1600 32 bit (Intel)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> from fractions import gcd
>>> gcd(10, 20)
10

Here's a quick test validating your routine:

from random import randint
from math import gcd

def gcf(num1, num2):
    list_fac = []
    x = max(num1, num2)
    y = min(num1, num2)

    for i in range(1, x + 1):
        if x % i == 0:
            list_fac.append(i)

            for t in list_fac:
                if y % t != 0:
                    list_fac.remove(t)

    return list_fac[-1] if list_fac else 0

if __name__ == "__main__":
    passes = 0
    tests = 10000

    for i in range(tests):
        a, b = randint(0, 100), randint(0, 100)

        if gcd(a, b) == gcf(a, b):
            passes += 1

    print(f"{passes}/{tests} passed") # => 10000/10000 passed

Quick benchmark:

gcd 0.7560891520042787
gcf 39.11557542099763
gcf improved 32.58505471699755

import timeit
from math import gcd

def gcf(num1, num2):
    list_fac = []
    x = max(num1, num2)
    for i in range(2,x + 1):
        if x % i == 0:
            list_fac.append(i)
            y = min(num1, num2)
            for t in list_fac:
                if y % t != 0:
                    list_fac.remove(t)

def gcf2(num1, num2):
    greatest = 0
    x = max(num1, num2)
    y = min(num1, num2)

    for i in range(1, x + 1):
        if x % i == 0 and y % i == 0:
            greatest = i

    return greatest

def a(): gcd(20, 125)
def b(): gcf(20, 125)
def c(): gcf2(20, 125)

if __name__ == '__main__':    
    print("gcd", timeit.timeit("a()", setup="from __main__ import a"))
    print("gcf", timeit.timeit("b()", setup="from __main__ import b"))
    print("gcf improved", timeit.timeit("c()", setup="from __main__ import c"))

My GCF/GCD program is returning an extra number

1 Answers1