By listing the first six prime number:2, 3, 5, 7, 11, and 13,we can see that the 6th prime is 13.What is the 10001st prime number?

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import math

def get_prime(n): #计算得到第n个质数
if(n == 1):
return 2
else:
m = 1 #记录质数的个数
a = 3 #从三开始验证质数
i = 2 #除数初始化
flag = True
while m != n:
while i <= math.sqrt(a):
if a % i == 0:
flag = Flase
break
i += 1
if flag:
m += 1
flag = True
a += 2 #每次加2,排除掉偶数
i = 2 #除数置2

return a - 2

上面的方法比较直接,在这题的解答中给出了一种更加有效率的方法。用了一下结论;

  • 1不是质数

  • 所有的质数除了2都是奇数

  • 大于三的质数都可以由6k +/- 1表示

  • 如果n找不到小于等于 根号n 的除数,那么n一定是质数

1
2
3
4
5
6
7
8
9
10
11
12
def fun(num):
if num == 1: return False
if num < 4: return True
if num % 2 == 0: reutrn False #能被2整除排除
if num % 3 == 0: return False #能被3整除排除
i = 5 #初始化除数
while i <= math.sqrt(num):
if n % i == 0: return False #第一次验证除数5,以后验证质除数
i
if n % (i + 2) == 0: return False
i += 6
return True

我又试了一下计算第100011个质数,上面那种方法用了一分钟左右,下面哪种用了13秒左右,成效还是很显著的。。还是也是比较久,我试试c语言。一秒不到,优势显著。不该拿python的弱势和c语言的优势比:)