common

求最大公约数

欧几里得方法

def gcd(p, q):
    if q == 0:
        return p
    else:
        r = p % q
        return gcd(q, r)

素数的判断

小于 2 肯定不是,大于 2 ,从 2 到检查的数的平方根,能被整除则是素数,否则不是。

二分查找

def binary_sort(array, key, start, end):
    if start > end:
        return -1
    middle = (start + end) // 2
    if key < array[middle]:
        return binary_sort(array, key, start, middle-1)
    elif key > array[middle]:
        return binary_sort(array, key, middle+1, end)
    else:
        return middle