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

Sep 22, 2020

#### 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 coprimedef 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 <= ndef 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 algorithmprint("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)]``

Younes Derfoufi
my-courses.net