Problem 7

Problem 7

28 December 2001

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

What is the 10001^st prime number?

def fun7():
  primes = [2]
  cnt    = 1
  i      = 3
  isPrime=True
  while cnt < 10001:
    isPrime = True
    for j in primes:
      if i%j == 0:
        i+=2
        isPrime = False
        break
    if not isPrime:
      continue

    primes.append(i)
    i   += 2
    cnt += 1
  print i-2, cnt

answer is 104743

速度有点慢，用了9秒。在判断是否为素数时

def fun7():
  primes = [2]
  cnt    = 1
  i      = 3
  isPrime=True
  while cnt < 10001:
    isPrime = True
    temp = math.sqrt(i)
    for j in primes:
      if j > temp:
        break

      if (i%j == 0):
        i+=2
        isPrime = False
        break
    if not isPrime:
      continue

    primes.append(i)
    i   += 2
    cnt += 1
  print i-2, cnt

代码运行时间可以缩短为0.296999931335