How can I get this Python code to run more quickly? [Project Euler Problem #7]_问答_开发者

I'm trying to complete this Project Euler challenge:

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?

My code seem to be right because it works with small numbers, e.g 6th prime is 13.

How can i improve it so that the code will run much more quickly for larger numbers such as 10 001.

Code is below:

#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 c开发者_JAVA百科ount != n:
        x += 1
        if is_prime(x) == True:
            count += 1
    print x


term(10001)

UPDATE:

Thanks for your responses. I should have been more clear, I am not looking to speed up the interpreter or finding a faster interpreter, because i know my code isn't great, so i was looking for ways of make my code more efficient.

A few questions to ponder:

Do you really need to check the division until n-1? How earlier can you stop?
Apart from 2, do you really need to check the division by all the multiples of two ?
What about the multiples of 3? 5? Is there a way to extend this idea to all the multiples of previously tested primes?

The purpose of Project Euler is not really to think learn programming, but to think about algorithms. On problem #10, your algorithm will need to be even faster than on #7, etc. etc. So you need to come up with a better way to find prime numbers, not a faster way to run Python code. People solve these problems under the time limit with far slower computers that you're using now by thinking about the math.

On that note, maybe ask about your prime number algorithm on https://math.stackexchange.com/ if you really need help thinking about the problem.

A faster interpreter won't cut it. Even an implementation written in C or assembly language won't be fast enough (to be in the "about one second" timeframe of project Euler). To put it bluntly, your algorithm is pathetic. Some research and thinking will help you write an algorithm that runs faster in a dog-slow interpreter than your current algorithm implemented in native code (I won't name any specifics, partly because that's your job and partly because I can't tell offhand how much optimization will be needed).

Many of the Euler problems (including this one) are designed to have a solution that computes in acceptable time on pretty much any given hardware and compiler (well, not INTERCAL on a PDP-11 maybe).

You algorithm works, but it has quadratic complexity. Using a faster interpreter will give you a linear performance boost, but the quadratic complexity will dwarf it long before you calculate 10,000 primes. There are algorithms with much lower complexity; find them (or google them, no shame in that and you'll still learn a lot) and implement them.

Without discussing your algorithm, the PyPy interpreter can be ridiculously faster than the normal CPython one for tight numerical computation like this. You might want to try it out.

to check the prime number you dont have to run till n-1 or n/2....

To run it more faster,you can check only until square root of n

And this is the fastest algorithm I know

def isprime(number):
        if number<=1:
            return False
        if number==2:
            return True
        if number%2==0:
            return False
        for i in range(3,int(sqrt(number))+1):
            if number%i==0:
                return False
        return True

As most people have said, it's all about coming up with the correct algorithm. Have you considered looking at a Sieve of Eratosthenes

import time
t=time.time()
def n_th_prime(n):

    b=[]
    b.append(2)
    while len(b)<n :
        for num in range(3,n*11,2):
            if all(num%i!=0 for i in range(2,int((num)**0.5)+1)):
                b.append(num)


    print list(sorted(b))[n-1]
n_th_prime(10001)
print time.time()-t

prints

104743

0.569000005722 second

A pythonic Answer

import time
t=time.time()
def prime_bellow(n):
   b=[]
   num=2
   j=0
   b.append(2)
   while len(b)-1<n:
        if all(num%i!=0 for i in range(2,int((num)**0.5)+1)):
            b.append(num)
        num += 1
   print b[n]
 prime_bellow(10001)
 print time.time()-t

Prints

104743

   0.702000141144 second

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

I approached it a different way. We know that all multiples of 2 are not going to be prime (except 2) we also know that all non-prime numbers can be broken down to prime constituents.

i.e.

12 = 3 x 4 = 3 x 2 x 2

30 = 5 x 6 = 5 x 3 x 2

Therefore I iterated through a list of odd numbers, accumulating a list of primes, and only attempting to find the modulus of the odd numbers with primes in this list.

#First I create a helper method to determine if it's a prime that 
#iterates through the list of primes I already have
def is_prime(number, list):
    for prime in list:
        if number % prime == 0:
            return False
    return True

EDIT: Originally I wrote this recursively, but I think the iterative case is much simpler

def find_10001st_iteratively():
    number_of_primes = 0
    current_number = 3
    list_of_primes = [2]
    while number_of_primes <= 10001:
        if is_prime(current_number, list_of_primes):
            list_of_primes.append(current_number)
            number_of_primes += 1
        current_number += 2
    return current_number

A different quick Python solution:

import math
prime_number = 4 # Because 2 and 3 are already prime numbers
k = 3 # It is the 3rd try after 2 and 3 prime numbers
milestone = 10001
while k <= milestone:
    divisible = 0
    for i in range(2, int(math.sqrt(prime_number)) + 1):
        remainder = prime_number % i
        if remainder == 0: #Check if the number is evenly divisible (not prime) by i
            divisible += 1
    if divisible == 0:
        k += 1
    prime_number += 1
print(prime_number-1)

import time
t = time.time()

def is_prime(n):   #check primes
    prime = True
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            prime = False
            break
    return prime

def number_of_primes(n):
    prime_list = []
    counter = 0
    num = 2
    prime_list.append(2)
    while counter != n:
        if is_prime(num):
            prime_list.append(num)
            counter += 1
        num += 1
    return prime_list[n]

print(number_of_primes(10001))
print(time.time()-t)

104743
0.6159017086029053

based on the haskell code in the paper: The Genuine Sieve of Eratosthenes by Melissa E. O'Neill

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)

prints:

[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)

prints:

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

prints: