#### 涓€浜涘垱寤鸿〃鐨勫疄渚�
##from math import sin, cos, tan
##
##x = [sin(1.0), cos(1.0), tan(1.0)]
##
##a1 = ["Beijing", "Shanghai", "Tianjin", "Guangzhou", "Chongqing"]
##
##a2 = [1, 2, 3]
##a2[2] = "a"
##print(a2)
##
##a3 = a1 + a2
##print(a3)
##
##a4 = a2 * 3
##print(a4)
##
##a5 = [0] * 20
##print(a5)
##
##a6 = [None] * 30
##print(a6)
##
##a7 = list(range(20))
##print(a7)
##
##clist = list("Beijing")
##for x in clist:
##    print(x, end=", ")
##    
##print("")


#### 璁＄畻琛ㄤ腑鍏冪礌涔嬪拰
##def sum(numbs):
##    s = 0
##    for i in range(len(numbs)):
##        s += numbs[i]
##    return s
##
##
##def sum(numbs):
##    s = 0
##    for x in numbs:
##        s += x
##    return s
##
##print(sum([45, 38, 873, 26]))


#### 鐢ㄨ〃琛ㄧず鍚戦噺锛屽畾涔夋眰鍚戦噺鐐圭Н鐨勫嚱鏁�
##def vec_prod(v1, v2):
##    if len(v1) != len(v2):
##        return 0.0
##    prod = 0.0
##    for i in range(len(v1)):
##        prod += v1[i] * v2[i]
##    return prod
##
##p = vec_prod([1.2, 5.3, 4.23, 7.44], [7.28, 9.6, 2.11, 6.53])
##print(p)


#### 姹傝处鍗曟€昏鐨勫嚱鏁�
#### 璐﹀崟鐢ㄨ〃琛ㄧず锛岃处鍗曞厓绱犱负 [鍗曚环, 鏁伴噺]
##inv1 = [[2.10, 12.4], [1.25, 2.44], [17.34, 3.6]]
##
##def sum_price0(invoice):
##    sum = 0.0
##    for entry in invoice:
##        sum += entry[0] * entry[1]
##    return sum
##
#### 瀹為檯涓�, Python 涓彲浠ユ妸绋嬪簭鍐欏緱鏇存竻鏅帮紝鍙互鐢ㄤ袱涓彉閲�
#### 鍒嗗埆鑾峰緱璐﹀崟琛ㄤ腑鍚勫厓绱犵殑涓や釜椤�
##def sum_price(invoice):
##    sum = 0.0
##    for price, quantity in invoice:
##        sum += price * quantity
##    return sum
##
##print("Total price: {:.2f}".format(sum_price(inv1)))


#### 姹傚寘鍚枑娉㈤偅濂戞暟鍒楃殑琛�
##fibs = [0]*20
##fibs[0] = fibs[1] = 1
##for i in range(2, 20):
##    fibs[i] = fibs[i-1] + fibs[i-2]
##
##print(fibs)
##
##
##def gfibs(n):
##    fibs = [0] * n
##    fibs[0] = fibs[1] = 1
##    for i in range(2, n):
##        fibs[i] = fibs[i-1] + fibs[i-2]
##    return fibs
##
##print("First {} Fibonacci numbers: {}".format(20, gfibs(20)))
##
##
#### 涓€椤归」鐢熸垚鍚庣敤 append 鏂规硶鍔犲湪琛ㄦ渶鍚�
##def gen_fibs(n):
##    fibs = [1, 1]
##    for i in range(2, n):
##        fibs.append(fibs[-2] + fibs[-1])
##    return fibs
##
##print("First {} Fibonacci numbers: {}".format(20, gen_fibs(20)))


## 姹傚椤瑰紡鐨勫€�
## 鍏朵腑澶氶」寮忕敤琛ㄨ〃绀猴紝琛ㄧ殑鍏冪礌琛ㄧず澶氶」寮忎腑鍚勬椤圭殑绯绘暟
## 璁� poly = [2, 4, 5, 3]
## 瀵瑰簲澶氶」寮忔槸 2 + 4 * x + 5 * x**2 + 3 * x**3
p1 = [1, 3, 3, 1]
p2 = [2, 5, 6, 2, 1]

#### 姹� p 鍦� x 鐨勫€�
##def eval_poly(p, x):
##    val = 0
##    for i in range(0, len(p)):
##        val += p[i] * x**i
##    return val
##
##print("Value of p1 in 1.0:", eval_poly(p1, 1.0))
##print("Value of p2 in 2.7:", eval_poly(p2, 2.7))


### 鐢ㄤ箻娉� * 涓嶇敤涔樻柟 ** 鐨勫嚱鏁板疄鐜�
##def eval_poly1(p, x):
##    val = 0.0
##    xi = 1
##    for i in range(0, len(p)):
##        val += p[i] * xi
##        xi *= x
##    return val

##print("Value of p1 in 1.0:", eval_poly1(p1, 1.0))
##print("Value of p2 in 2.7:", eval_poly1(p2, 2.7))


### 鍙︿竴绉嶅疄鐜�
### range(len(p)-1, -1, -1) 缁欏嚭搴忓垪  
### len(p)-1, len(p)-2, ..., 2, 1, 0,
### 鍏朵腑鍖呮嫭 0, 姝ラ暱涓� -1.
##def eval_poly2(p, x):
##    val = 0.0
##    for i in range(len(p)-1, -1, -1):
##        val = val * x + p[i]
##    return val
##
##print("Value of p1 in 1.0:", eval_poly2(p1, 1.0))
##print("Value of p2 in 2.7:", eval_poly2(p2, 2.7))
##
##
##def eval_poly3(p, x):
##    val = 0
##    for a in reversed(p):
##        val = val * x + a
##    return val
##
##print("Value of p1 in 1.0:", eval_poly3(p1, 1.0))
##print("Value of p2 in 2.7:", eval_poly3(p2, 2.7))


## 鐢ㄧ瓫娉曟眰鐩村埌 n 鐨勭礌鏁拌〃
## 鐢ㄤ竴涓〃瀛樺偍鐩村埌 n 鐨勬暣鏁帮紝浠� 2 寮€濮嬶紝瀵规瘡涓凡鐭ョ礌鏁帮紝
## 灏嗗叾鍊嶆暟绛涢櫎锛堝皢瀵瑰簲浣嶇疆鐨勫厓绱犵疆 0锛�
##def sieve(n):
##    if n < 2:
##        return []
##    numbs = list(range(n+1))
##    numbs[0] = numbs[1] = 0
##    k = 2
##    while k * k <= n:
##        if numbs[k] != 0:
##            for i in range(2 * k, n + 1, k):
##                numbs[i] = 0
##        k += 1
##        
##    return numbs
##
##for n in sieve(100):
##    if n != 0:
##        print(n, end=" ")
##print("")


##### 鐢熸垚鐩村埌 n 鐨勭礌鏁拌〃
def sieve(n):
    if n < 2:
        return []
    numbs = list(range(n+1))
    numbs[0] = numbs[1] = 0
    k = 2
    while k * k <= n:
        if numbs[k] != 0:
            for i in range(2*k, n+1, k):
                numbs[i] = 0
        k += 1

    primes = []
    for x in numbs:
        if x != 0:
            primes.append(x)
    return primes