HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Basic prime summation

Submitted by: @import:stackexchange-codereview··
0
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 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 total


Or 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 True

Code Snippets

amount = 1
total = 2
candidate = 3
while amount < b:
    if is_prime(candidate):
        amount += 1
        total += candidate
    candidate += 2

return total
import 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 True

Context

StackExchange Code Review Q#111521, answer score: 3

Revisions (0)

No revisions yet.