python小练

素数筛：

 1 isprime = []
 2 ans = []
 3 
 4 for i in range(0, 101):
 5     isprime.append(True)
 6 isprime[0] =  False
 7 isprime[1] = False
 8 for i in range(2, 11):
 9     if isprime[i] == True:
10         t = int(100 / i) + 1
11         for j in range(2, t):
12             isprime[i*j] = False
13 
14 for i in range(1, 101):
15     if isprime[i] == True:
16         ans.append(i)
17 # for i in ans:
18 #     print i,
19 # print

View Code

最大公因数：

1 def gcd(a, b):
2     if b == 0:
3         return a
4     else:
5         return gcd(b, a % b)

View Code

二进制下a有几个1：

1 def cnt(a):
2     cnt = 0
3     while a:
4         a = a & (a - 1)
5         cnt += 1
6     return cnt
7 
8 print(cnt(a))

View Code

KMP算法：

 1 a = "abcdabc"
 2 b = "abc"
 3 na = len(a)
 4 nb = len(b)
 5 pre = [0] * 100
 6 pre[0] = -1
 7 j = 0
 8 k = -1
 9 while(j < nb):
10     if k == -1 or b[j] == b[k] :
11         j += 1
12         k += 1
13         pre[j] = k
14     else:
15         k = pre[k]
16 ans = 0
17 i = 0
18 j = 0
19 while(i < na):
20     if a[i] == b[j] or j == -1:
21         i += 1
22         j += 1
23     else:
24         j = pre[j]
25     if j == nb:
26         j = 0   #res.append(j)
27         ans = 1
28 if ans == 1:
29     print("YES")
30 else:
31     print("NO")
32

View Code