CODEWITHSUNDEEP
python
user2827356
user2827356

Reputation: 3

Coprime Factorization in Python

I have to write a code to find the two highest co prime factors of an entered number, 10^num.

Right now, I've written:

def coprimes(num):
    for x in range (2, num):
        for y in range (2, num):
            while (gcd(x,y) == 1) & (x != y):
                if (x*y==num):
                    return (x,y)

Which is obviously a really slow program because of the forloops. Whenever I enter it into the terminal, it's too slow to produce an answer. I'm also not sure if this is correct. Do you have any suggestions on how I could improve this method?

An example answer of this method should be:

>>> coprimes(10)
(9765625, 1024)

Upvotes: 0

Views: 1281

Answers (1)

user2357112
user2357112

Reputation: 280251

You want

return 2**num, 5**num

Note that the question is ill-defined - it's not clear whether 2**num, 5**num should be considered higher than 1, 10**num. However, those pairs of factors are higher than any other.

To arrive at this answer, note that at most 1 of the factors can be divisible by 2, and at most 1 of the factors can be divisible by 5. If one factor is divisible by both 2 and 5, the other must be 1, and any integer is coprime to 1. If one factor is divisible by 2 and the other by 5, we pick the highest powers of 2 and 5 possible. (Options where 2 or 5 divide neither number produce lower factors.)

Upvotes: 2

Related Questions