Solution Exercise 761: algorithm python to finds all tuples of coprime numbers verifying some condition

Exercise 761

Write an algorithm in python as a function which takes as parameters an integer n and which returns the list of integers tuples (p, q) such that p and q are prime between them and p + q less than or equal to n

Solution

# creating a function that test if given two numbers are coprime
def testCoprim(p , q):
    # initializing the number of common divisors
    commonDiv = 0
    for i in range(1 , p + 1):
        # we test if i is common divisor for p and q
        if (p%i == 0 and q%i == 0):
            # and then we increment commonDiv
            commonDiv = commonDiv + 1
    # p and q are coprime if and only if commonDiv = 1
    if (commonDiv == 1):
        return True
    else:
        return False

# creating the function that finds all tuples of coprime numbers (p,q) such that p + q <= n
def searchTuples(n):
    
    # initializing the list of searched tuples
    searchedList = []
    for i in range(1 , n + 1):
        for j in range(1 , n + 1):
            # we test if i and j are coprime and i + j <= n
            if ( testCoprim(i,j) and i + j <= n ):
                searchedList.append((i,j))
    return searchedList
# testing algorithm
print("The list of all coprime numbers (p,q) such that p + q <= 6 is L = ", searchTuples(6))
# The output is : The list of all coprime numbers (p,q) such that p + q <= 6 is L =  [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 1), (2, 3), (3, 1), (3, 2), (4, 1), (5, 1)]