#### 一些创建表的实例
##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