题解 | #集合的所有子集(一)#

class Solution:
    def gcd(self , a: int, b: int) -> int:
        big = max(a, b)
        small = min(a, b)
        sqrt_small = int(small ** 0.5)
        result = 1
        
        if big % small == 0:
            return small
        
        gys = 2
        while gys<=sqrt_small and result<=(small>>1):
            if small % gys == 0:
                re_gys = small//gys
                if big % re_gys == 0:
                    return re_gys
                elif big % gys == 0:
                    result *= gys
                    small = small // gys
                    big = big // gys
                    continue
            gys += 1
        return result

好像时间复杂度不是O(logn),是O(sqrt(n))