python笔记

计算素数比较快的方法

计算素数里面除数最大值用(int(prime ** 0.5) +1) ,最好不要用(prime / 2 + 1).在素数值非常大的时候,这两者差距非常明显.
比如104729的开方值:323
除以2的值是52365

再就是尽量用函数返回Ture Flase的判断,

例如: 求第10000个素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
prime = 2
number = 4
def is_prime(num):
    for x in range(2, int((num ** 0.5)) + 1):
        if num % x == 0:
            return False
    return True
while 1:
    if is_prime(number):
        prime += 1
    if prime == 10000:
        break
    number += 1
print number

用时0.5秒得出结果:104729

如果是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
prime = 2
number = 4
def is_prime(num):
    for x in range(2, int((num / 2)) + 1):
        if num % x == 0:
            return False
    return True
while 1:
    if is_prime(number):
        prime += 1
    if prime == 10000:
        break
    number += 1
print number

用时42秒,得出结果104729

如果是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
prime = 2
number = 4
while 1:
    flag = 0
    for i in range(2, int(number ** 0.5) + 1):
        if number % i == 0:
            flag = 1
    if flag == 0:
        prime += 1
    if prime == 10000:
        break
    number += 1
print number

用时3.0秒,得出结果104729