Как я могу заставить этот код Python работать быстрее? [Проект Эйлера Проблема № 7]

Question

Я пытаюсь выполнить эту задачу Project Euler:

Перечислив первые шесть простых чисел: 2, 3, 5, 7, 11 и 13, мы увидим, что 6-е числопростое число 13.

Что такое 10 001-е простое число?

Мой код кажется правильным, потому что он работает с небольшими числами, например, 6-е простое число - 13.

Как я могу улучшить его, чтобы код работал намного быстрее для больших чисел, таких как 10 001.

Код указан ниже:

#Checks if a number is a prime
def is_prime(n):
    count = 0
    for i in range(2, n):
        if n%i == 0:
            return False
            break
        else:
            count += 1
    if count == n-2:
        return True

#Finds the value for the given nth term     
def term(n):
    x = 0
    count = 0
    while count != n:
        x += 1
        if is_prime(x) == True:
            count += 1
    print x


term(10001)

ОБНОВЛЕНИЕ:

Спасибо за ваши ответы.Я должен был быть более ясным, я не стремлюсь ускорить интерпретатор или найти более быстрый интерпретатор, потому что я знаю, что мой код не очень хорош, поэтому я искал способы сделать мой код более эффективным.

Answer 1

import math

count = 0 <br/> def is_prime(n):
    if n % 2 == 0 and n > 2:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

for i in range(2,2000000):
    if is_prime(i):
        count += 1
        if count == 10001:
            print i
            break

Answer 2

Как говорили большинство людей, все дело в том, чтобы придумать правильный алгоритм. Рассматривали ли вы, глядя на Сито Эратосфена

Answer 3

на основе кода haskell в статье: Подлинное сито эратосфена Мелиссы Э. О'Нил

from itertools import cycle, chain, tee, islice

wheel2357 = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]

def spin(wheel, n):
    for x in wheel:
        yield n
        n = n + x

import heapq

def insertprime(p,xs,t):
    heapq.heappush(t,(p*p,(p*v for v in xs)))

def adjust(t,x):
    while True:
        n, ns = t[0]
        if n <= x:
            n, ns = heapq.heappop(t)
            heapq.heappush(t, (ns.next(), ns))
        else:
            break

def sieve(it):
    t = []
    x = it.next()
    yield x
    xs0, xs1 = tee(it)
    insertprime(x,xs1,t)
    it = xs0
    while True:
        x = it.next()
        if t[0][0] <= x:
            adjust(t,x)
            continue
        yield x
        xs0, xs1 = tee(it)
        insertprime(x,xs1,t)
        it = xs0

primes = chain([2,3,5,7], sieve(spin(cycle(wheel2357), 11)))

from time import time
s = time()
print list(islice(primes, 10000, 10001))
e = time()
print "%.8f seconds" % (e-s)

печать:

[104743]
0.18839407 seconds

---

from itertools import islice
from heapq import heappush, heappop

wheel2357 = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,
             4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]

class spin(object):
    __slots__ = ('wheel','o','n','m')
    def __init__(self, wheel, n, o=0, m=1):
        self.wheel = wheel
        self.o = o
        self.n = n
        self.m = m
    def __iter__(self):
        return self
    def next(self):
        v = self.m*self.n
        self.n += self.wheel[self.o]
        self.o = (self.o + 1) % len(self.wheel)
        return v
    def copy(self):
        return spin(self.wheel, self.n, self.o, self.m)
    def times(self, x):
        return spin(self.wheel, self.n, self.o, self.m*x)

def adjust(t,x):
    while t[0][0] <= x:
        n, ns = heappop(t)
        heappush(t, (ns.next(), ns))

def sieve_primes():

    for p in [2,3,5,7]:
        yield p

    it = spin(wheel2357, 11)

    t = []
    p = it.next()
    yield p
    heappush(t, (p*p, it.times(p)))

    while True:
        p = it.next()
        if t[0][0] <= p:
            adjust(t,p)
            continue
        yield p
        heappush(t, (p*p, it.times(p)))

from time import time
s = time()
print list(islice(sieve_primes(), 10000, 10001))[-1]
e = time()
print "%.8f seconds" % (e-s)

печать:

104743
0.22022200 seconds

---

import time
from math import sqrt

wheel2357 = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]

list_prime = [2,3,5,7]

def isprime(num):
    limit = sqrt(num)
    for prime in list_prime:
        if num % prime == 0: return 0
        if prime > limit: break
    return 1

def generate_primes(no_of_primes):
    o = 0
    n = 11
    w = wheel2357
    l = len(w)
    while len(list_prime) < no_of_primes:
        i = n
        n = n + w[o]
        o = (o + 1) % l
        if isprime(i): 
            list_prime.append(i)

t0 = time.time()
generate_primes(10001)
print list_prime[-1]        # 104743
t1 = time.time()
print t1-t0                 # 0.18 seconds

печать:

104743
0.307313919067