patternpythonMinor
Basic prime summation
Viewed 0 times
summationprimebasic
Problem
I wrote basic Python code for the summation of n primes. It works but I wanted to find out how I could improve it and what shortcuts I missed.
""" So this program is designed to add up the first 'b' primes
==> Prime number is defined as a number only divisible by itself or 1"""
def is_prime(a):
""" This function determines if a number is prime"""
pri = True
n = 2
while n < a:
if a % n == 0:
pri = False
n += 1
return pri
def addition_of_primes(b):
""" This function will find the first b primes.
It stores each one in a list and then we take
the sum of that list"""
primes = []
candidate = 2
while len(primes) < b:
if is_prime(candidate):
primes.append(candidate)
candidate += 1
return sum(primes)
print addition_of_primes(1000)Solution
Ignoring the 'use a different algorithm' approach. (Even though the Sieve of Eratosthenes is better).
There are two very common optimisations you missed in the prime checker.
-
You can increment by 2, so you skip all the even numbers.
-
You can
There is another less common optimisation.
There is also a rare algorithm, that goes in steps of 6.
But that's uncommon, and if you need that speed, use the Sieve.
As for your
I would not build up an intermarry list.
One way to do that is:
Or if you want this all in one line:
If you add the optimisations to
There are two very common optimisations you missed in the prime checker.
-
You can increment by 2, so you skip all the even numbers.
-
You can
return False early to avoid waisted CPU cycles.There is another less common optimisation.
- Going to the square root of
n.
There is also a rare algorithm, that goes in steps of 6.
But that's uncommon, and if you need that speed, use the Sieve.
As for your
addition_of_primes function,I would not build up an intermarry list.
One way to do that is:
amount = 1
total = 2
candidate = 3
while amount < b:
if is_prime(candidate):
amount += 1
total += candidate
candidate += 2
return totalOr if you want this all in one line:
import itertools
return sum(itertools.islice(itertools.ifilter(is_prime, itertools.count(2)), b))If you add the optimisations to
is_prime, you should get:def is_prime(num):
if num == 2:
return True
if num % 2 == 0:
return False
for div in xrange(3, int(num ** 0.5) + 1, 2):
if num % div == 0:
return False
return TrueCode Snippets
amount = 1
total = 2
candidate = 3
while amount < b:
if is_prime(candidate):
amount += 1
total += candidate
candidate += 2
return totalimport itertools
return sum(itertools.islice(itertools.ifilter(is_prime, itertools.count(2)), b))def is_prime(num):
if num == 2:
return True
if num % 2 == 0:
return False
for div in xrange(3, int(num ** 0.5) + 1, 2):
if num % div == 0:
return False
return TrueContext
StackExchange Code Review Q#111521, answer score: 3
Revisions (0)
No revisions yet.