CODEWITHSUNDEEP
pythonperformancehelper
Lu MON
Lu MON

Reputation: 107

how to make this code on python run faster?

I wrote this snippet on python to resolve project Euler problem #10, but i've been waiting 15 minutes (running this code) and it still doesn't end.

Please help me to improve this code or optimize it.

Here is the snippet:

def prime (n):
  f = 1 #flag
  for i in range(2,n):
    if n % i == 0:
        f = 0
  return f

s = 0 # Sum
for i in range(2,2000000):
if prime(i) == 1:
    s = i  +  s
print s

Upvotes: 2

Views: 155

Answers (2)

Namit Singal
Namit Singal

Reputation: 1516

If you want all prime numbers till 2000000, you should consider using Sieve of Eratosthenes.

Code in python : - 

def eratosthenes2(n):
    multiples = set()
    for i in range(2, n+1):
        if i not in multiples:
            yield i
            multiples.update(range(i*i, n+1, i))

print(list(eratosthenes2(2000000)))

Source - http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Python

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Upvotes: 1

Konstantin
Konstantin

Reputation: 25369

import math

def prime (n):
    for i in xrange(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

s = 2 # Sum
for i in xrange(3,2000000, 2):
    if prime(i):
        s += i
print s

It runs in less than 10 seconds for me.

First of all, you want to return from prime once you found out, that a numer is composite.

Second, you do not want to check even numbers. Skip them with xrange(3,2000000, 2)

Third, there is no need to check all numbers from 2 to n in prime, because a*b = b*a

Since you use Python 2 I've replaced range with xrange, it will be a little bit more efficient.

Upvotes: 4

Related Questions