math.gcd（）与欧几里德算法

Question

导入math库或

def computegcd(x,y):
    while(y):
        x,y = y,x%y
    return x

Answer 1

您可以使用^{}自己检查：）

运行以下命令：

from timeit import timeit
import math
import random

x = random.randint(9 ** 6, 9 ** 7)
y = random.randint(5 ** 5, 5 ** 6)


def with_math():
    return math.gcd(x, y)


def with_euclid():
    xx = x
    yy = y
    while yy:
        xx, yy = yy, xx % yy
    return xx


print(with_math() == with_euclid())  # Make sure result is same
print(timeit(with_math, number=10**7))
print(timeit(with_euclid, number=10**7))

在我当前的笔记本电脑上，它输出：

True
3.021651975000168
7.143860205000237