#最大公约数
def gcd(a, b):
    while b:
        a, b = b, a%b 
    return a 

a = 21
b = 9
print(gcd(a, b))  # 最大公约数
print(a*b/gcd(a,b))  # 最小公倍数



# 多个数的gcd
def arr_gcd(A):
    gcd = A[0]
    for a in A:
        while a:
            gcd, a = a, gcd % a
    return gcd 

print(arr_gcd([3, 6, 21]))

# 素数筛选
import math

maxInteger = 1000000
prime = [True]*maxInteger
prime[0] = False
prime[1] = False

for i in range(2, (int)(math.sqrt(maxInteger)+1)):
    if prime[i]:
        for j in range(i*i, maxInteger, i):
            prime[j] = False
print(prime[11])

# 合并有序链表
import numpy as np 

class ListNode(object):
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

a = ListNode(1, ListNode(2, ListNode(3)))

b = ListNode(1, ListNode(4, ListNode(5)))

def sort_listnode(a, b):
    result = ListNode(0)
    cur = result
    if a is None:
        return b
    if b is None:
        return a 
    while a and b:
        if a.val < b.val:
            result.next = a
            a = a.next
        else:
            result.next = b
            b = b.next
        result = result.next
    if a is None:
        result.next = b
    if b is None:
        result.next = a 
    return cur.next
 
result = sort_listnode(a, b)

while result:
    print(result.val)
    result = result.next