Solution Exercise 516: python algorithm which determines the list of tuples whose gcd is equal to 3

Exrcise 516

Write a Python algorithm which determines among the integers less than or equal to a given integer n, all the list of tuples of integers (i , j) whose greatest common divisor d = gcd (i , j) = 3

Solution

# Create a function which determines the gcd of two integers.
def findGCD(m,n):
    # initialize the gcd of m and n
    d = m
    while(m%d !=0 or n%d != 0):
        d = d -1
    return d

def tuplesList(n):
    listTuples = []
    for i in range(1 , n + 1):
        for j in range(1 , n + 1):
            if findGCD(i , j) == 3:
                listTuples.append((i,j))
    return listTuples

# Testing algorithm for n = 100 
print("The searchd list is : " , tuplesList(100))