Why does Python's math.gcd run so fast ?

Revision en5, by kzoacn, 2017-11-23 15:33:17

I write two code to compute gcd in python3, but math.gcd is much faster than gcd.

Here is my code.

def gcd(a, b): 
	while a:
		a, b = b % a, a
	return b
x, y = map(int, input().split())
print(gcd(x, y))

And another code.

import math
x, y = map(int, input().split())
print(math.gcd(x, y))

What's the implemention of math.gcd? Thanks in advance.

Tags python, gcd, efficiency

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English kzoacn 2017-11-23 15:33:17 16
en4 English kzoacn 2017-11-23 15:32:56 56
en3 English kzoacn 2017-11-23 15:32:23 45
en2 English kzoacn 2017-11-23 15:31:49 32
en1 English kzoacn 2017-11-23 15:31:18 507 Initial revision (published)