find 2 largest equal numbers

[Frankduc]

As Deanhystad already said, for large numbers lack of efficiency can become a problem of this algorithm and he showed some enhancements. And Gribouillis already hinted to the extended Euclide algorithm.

I found an enhancement that is quite easy to explain. It is based on the fact that when you find that 42 is divisible by 2, you also know 42 is divisible by (42 / 2 =) 21. You have so to say two answers in one strike: one to add to the head of the result set and one to the tail.
And thinking this over there is no need to test all numbers in range(1, 42+1). Because: when you found that 21 is the first denominator below 42, then you do not have to test the range(22, 42+1).
Looking careful at this, you will notice you can stop checking numbers as soon as the head (low number) passes the tail (high number).

def denominators(x: int) -> set:
    """ Returns set of denominators for x . """
    result = set()
    for low_value in range(1, x):
        high_value = x // low_value
        # If the low_value exceeds the high_value there is no need to continue.
        if low_value > high_value:
            print("DEBUG finishing at: ", low_value)
            break
        else:
            if x % low_value == 0:
                result.add(low_value)
                result.add(high_value)
                print("DEBUG add: ", low_value, high_value)
    print("DEBUG return: ", result)
    return result

When testing this with 42 and a somewat larger number (10.003) you can see how it works.

a = 42
b = 10003
denom_a = denominators(a)
denom_b = denominators(b)
print(a, denom_a)
print(b, denom_b)
print("Common: ", denom_a & denom_b)

Output:
DEBUG add:  1 42
DEBUG add:  2 21
DEBUG add:  3 14
DEBUG add:  6 7
DEBUG finished at:  7
DEBUG return:  {1, 2, 3, 6, 7, 42, 14, 21}

DEBUG add:  1 10003
DEBUG add:  7 1429
DEBUG finished at:  101
DEBUG return:  {1, 10003, 1429, 7}

42 {1, 2, 3, 6, 7, 42, 14, 21}
10003 {1, 10003, 1429, 7}

Common:  {1, 7}

Here you can see the analysis of the first number finishes at 7 because this would result in the pair {7, (42/7=)6} but we already had that pair when the loop variable was 6: {6, (42/6=)7}.

In the second example you can see the numbers to be inspected is dramatically decreased, it finishes when the loop variable reaches 101, long before the end (10.003) is reached.

By the way @Frankduc , I am still curious about your C# program.

Your suggestion is not very far from my first attempt. You can see the same principal applied here with 2 while loop (less efficent):

num1 = 20
num1_list = []
num2 = 40
num2_list = []
x = 1
y = 1
while x <= num1:
    if num1 % x == 0:
        num1_list.append(x)
    x += 1
while y <= num2:
    if num2 % y == 0:
        num2_list.append(y)
    y += 1
xy = list(set(num1_list).intersection(num2_list))
print(xy[-1])
print("1NUM",num1_list)
print("2Num",num2_list)
print("xy",xy)
print("GCD",max(xy))

But considering the number of lines it still better than GFG solution:

def gcd(a, b):
  
    # Everything divides 0
    if (a == 0):
        return b
    if (b == 0):
        return a
  
    # base case
    if (a == b):
        return a
  
    # a is greater
    if (a > b):
        return gcd(a-b, b)
    return gcd(a, b-a)
  
# Driver program to test above function
a = 156
b = 56
if(gcd(a, b)):
    print('GCD of', a, 'and', b, 'is', gcd(a, b))
else:
    print('not found')

You wonder why so many if and else just to end up with:

def gcd(a, b):
  if b == 0:
    return a   
  else:
    return gcd(b, (a % b))
     
print(gcd(12, 4))

In the end its how the coder see the problem that dictate the approach.

For the C# its the same code as above, i was just trying to find a way to cross the list with : list(set(num1_list).intersection(num2_list)) i just did not know how. Amusing thing by searching i have found so many ways to intersect the lists.

Right now i am analyzing adding fraction from GFG and their solution make my head spin:

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


def lowest(den3, num3): 

   
    common_factor = gcd(num3, den3); 

  
    den3 = int(den3 / common_factor); 
    num3 = int(num3 / common_factor);
    print(num3, "/", den3);


def addFraction(num1, den1, num2, den2): 

   
    den3 = gcd(den1, den2); 

    den3 = (den1 * den2) / den3; 
    num3 = ((num1) * (den3 / den1) + 
            (num2) * (den3 / den2)); 

    
    lowest(den3, num3); 

num1 = 1; den1 = 500; 
num2 = 2; den2 = 1500; 

print(num1, "/", den1, " + ", num2, "/", 
      den2, " is equal to ", end = ""); 
addFraction(num1, den1, num2, den2);

I mean in my head it is more simple to just use the den and num multiplication and then reduce the fraction:

from fractions import Fraction

f1_nume = int(input('Enter the numerator for 1st fraction :'))
f1_deno = int(input('Enter the denominator for the 1st fraction :'))
f2_nume = int(input('Enter the numerator for 2nd fraction :'))
f2_deno = int(input('Enter the denominator for the 2nd fraction :'))

if(f1_deno == f2_deno):
  
    fraction = f1_nume + f2_nume
  
    print('Addition of two fractions are :' + str(Fraction) + '/' + str(f1_deno))

else:
   
    fraction = (f1_nume * f2_deno) + (f2_nume * f1_deno)
    print('Addition of fractions are :' + str(fraction) + '/' + str(f1_deno * f2_deno))
    
    print(Fraction(fraction, (f1_deno * f2_deno)))

Anyway the better you master python the more efficient is your code. Since i am as competent in C# than Python, i still got a lot of learning to do.