Sunday, 29 September 2013

Coprime Factorization in Python

Coprime Factorization in Python

I have to write a code to find the two highest co prime factors of an
entered number.
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)

No comments:

Post a Comment