## Tuesday, September 22, 2020

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)]``````

Younes Derfoufi
my-courses.net 