欧拉计划第七题

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

题意:求第10001个素数

判断一个数是否为素数,主要看它是否有质因子,比如看12 = 2*6,就不是素数。

这个数的平方根则在两个质因子的中间或者就是平方根本身,按照这个思路遍历自然数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from itertools import count
import math
import time
countNum =4
t0 = time.clock()
for i in count(11):
sqrtNum = int(math.sqrt(i))
flag = False
for j in range(2,sqrtNum+1):
if i%j ==0:
flag=True
if not flag:
countNum+=1

if countNum==10001:
print(time.clock()-t0)
print(i)
break

最后结果是104743

耗时2.27s