CODEWITHSUNDEEP
pythonfunctiongreatest-common-divisor
mattryan8524
mattryan8524

Reputation: 7

Smallest Coprime

I am writing two functions. the first functions goal is to take two numbers as parameters, and return true if they are co-prime and false if otherwise. this function is working properly, and looks like this:

from math import gcd #imports GCD function
def check_co_prime(num, M):
    return gcd(num, M) == 1

For the second function, I want to take one number, M, as a parameter. And then have it return the smallest coprime of M that is greater than 1. I think theres a way to use the first function to help me write my second function, but I am having trouble. This is what I have, but it hasn't been getting me the desired output.

from math import gcd        
def get_smallest_co_prime(M):
    if gcd(M)>1:
        return gcd(M)





    TypeError: gcd() takes exactly 2 arguments (1 given)

Upvotes: 0

Views: 2451

Answers (1)

Kevin L.
Kevin L.

Reputation: 1471

My solution:

from math import gcd        

def check_co_prime(num, M):
    return gcd(num, M) == 1 

def get_smallest_co_prime(M):
    for i in range(2, M): # for every number *i* starting from 2 up to M
        if check_co_prime(i, M): # check if *i* is coprime with M
            return i # if it is, return i as the result

Since the algorithm starts from i = 2 and continues in increasing order (i.e. i=2,3,4 etc... ), the first value of i to satisfy the if condition will be the smallest number that is coprime with M.

Upvotes: 1

Related Questions