python sum of primes

Question

I am tying to make a python program that will generate the sum of primes for a number, but the program is not giving the correct result,please tell me why.

b=1
#generates a list of numbers.
while b<100:
    b=b+1
    x = 0.0
    a = 0
    d = 0
    #generates a list of numbers less than b. 
    while x<b:
        x=x+1
        #this will check for divisors. 
        if (b/x)-int(b/x) == 0.0:
            a=a+1
        if a==2:
            #if it finds a prime it will add it.
            d=d+b
print d 

I made it generate a list of primes successfully, but i could not get the primes to add.

This is the code that i used to generate a list of primes.

b=1
while b<1000:
    b=b+1
    n = b
    x = 0.0
    a = 0
    while x<n:
        x=x+1
        if (n/x)-int(n/x) == 0.0:
            a=a+1
    if a==2:
        print b

Answer 1

Kevin properly answered the question you asked. Permit me to answer the question you didn't ask, but should have: What is the best way to compute the sum of the primes less than n. The answer is to use a sieve:

def sumPrimes(n):
    sum = 0
    sieve = [True] * (n+1)
    for p in range(2, n):
        if sieve[p]:
            sum += p
            for i in range(p*p, n, p):
                sieve[i] = False
    return sum

This code implements the Sieve of Eratosthenes, summing primes as it goes. It works by repeatedly choosing the smallest uncrossed number (p in the code above, which is selected when sieve[p] is True), then crossing out all of its multiples (i in the code above, which is incremented by p to compute multiples of p) starting from its square (since all smaller composites have already been crossed out). A sample use of the function is print sumPrimes(100), which prints 1060, which is the correct answer.

Note that Roland's answer does not implement the Sieve of Eratosthenes, even though he claims that it does; use of the modulo function is the giveaway that Roland's answer uses trial division, not the Sieve of Eratosthenes.

If you're interested in programming with prime numbers, I modestly recommend this essay at my blog.

Answer 2

if you're doing this for the sake of learning python there are more concise (>> less error-prone) ways of doing this. From your question I'm assuming you're trying to sum all the prime numbers below and including 100:

sum=0
limit=100
for n in range(2,limit+1):
  if all(n % i for i in range(2, n)):
    sum += n
print sum

prints 1060

Answer 3

Just sum the list using the code you used to generate the list:

d = sum(d)
print d

Answer 4

Your d variable is being reset during each iteration of your outer loop. Move the initialization out of that loop.

Additionally, the a == 2 check should only occur once per iteration of the outer loop. Move it out of the inner loop.

b=1
d = 0
#generates a list of numbers.
while b<100:
    b=b+1
    x = 0.0
    a = 0
    #generates a list of numbers less than b. 
    while x<b:
        x=x+1
        #this will check for divisors. 
        if (b/x)-int(b/x) == 0.0:
            a=a+1
    if a==2:
        #if it finds a prime it will add it.
        d=d+b
print d 

Result:

1060

While we're at it, let's try cleaning up the code so it's more comprehensible. You can move the inner loop into its own function, so readers can more clearly understand its purpose:

def is_prime(b):
    x = 0.0
    a = 0
    while x<b:
        x=x+1
        #this will check for divisors. 
        if (b/x)-int(b/x) == 0.0:
            a=a+1
    if a==2:
        return True
    else:
        return False

b=1
d=0
#generates a list of numbers.
while b<100:
    b=b+1
    if is_prime(b):
        d=d+b
print d

It's also useful to use variable names that describe what they represent:

def is_prime(number):
    candidate_factor = 0
    amount_of_factors = 0
    while candidate_factor<number:
        #A += B is equivalent to A = A + B
        candidate_factor += 1
        #A little easier way of testing whether one number divides another evenly
        if number % candidate_factor == 0:
            amount_of_factors += 1
    if amount_of_factors == 2:
        return True
    else:
        return False

number=1
prime_total=0
#generates a list of numbers.
while number<100:
    number += 1
    if is_prime(number):
        prime_total += number
print prime_total

for loops are more idomatic than while loops that increment a counter:

def is_prime(number):
    amount_of_factors = 0
    for candidate_factor in range(1, number+1):
        if number % candidate_factor == 0:
            amount_of_factors += 1
    if amount_of_factors == 2:
        return True
    else:
        return False

prime_total=0
#generates a list of numbers.
for number in range(2, 101):
    if is_prime(number):
        prime_total += number
print prime_total

If you're feeling bold, you can use list comprehensions to cut down on the number of loops you use:

def is_prime(number):
    factors = [candidate_factor for candidate_factor in range(1, number+1) if number % candidate_factor == 0]
    return len(factors) == 2

#generates a list of numbers.
primes = [number for number in range(2, 101) if is_prime(number)]
prime_total = sum(primes)
print prime_total

Answer 5

def sum_of_prime(num):
        if num < 2:
            return 'Please enter values greater than 2'
        if num == 2:
                return 2
        sum = 0
        for j in range(2,num):
                for i in range(2,j):
                        if (j % i) == 0:
                                break
                else:
                        print j
                        sum = sum + j
        return sum
num = int(raw_input())
result = sum_of_prime(num)
print result

Answer 6

List comprehensions are a powerful tool in Python. Think of them as a for-loop in steroids. :-) You can use them to implement trial division, which is a simple way of finding primes.

It works like this:

In [4]: sum(prime_list(100))
Out[4]: 1061

The prime_list function:

def prime_list(num):
    """Returns a list of all prime numbers up to and including num.
    Based on trial division.

    :num: highest number to test
    :returns: a list of primes up to num

    """
    if num < 3:
        raise ValueError('this function only accepts arguments > 2')
    candidates = range(3, num+1, 2) # (a)
    L = [c for c in candidates if all(c % p != 0 for p in range(3, c, 2))] #(b)
    return [1, 2] + L

Now for the explanation. With the exception of 2, all prime numbers are odd. So all the odd numbers from 3 to num (100 in this case) are candidates for prime numbers. Let's generate a list of those as done at (a):

In [5]: num = 100

In [6]: range(3, num+1, 2)
Out[6]: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99]

For an odd number c to be prime, one must ensure that c modulo all previous odd numbers p must be non-zero. Let's say c is 25.

In [7]: c = 25

Then p is in:

In [8]: range(3, c, 2)
Out[8]: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23]

Now check c modulo p:

In [9]: [c % p != 0 for p in range(3, c, 2)]
Out[9]: [True, False, True, True, True, True, True, True, True, True, True]

As we know 25 % 5 == 0, so the second item in the list is False. However, for a number to be prime, all items in the list must be true:

In [10]: all(c % p != 0 for p in range(3, c, 2))
Out[10]: False

So 25 is not a prime.

Let's try again for c is 41:

In [11]: c = 41

In [12]: range(3, c, 2)
Out[12]: [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39]

In [13]: [c % p != 0 for p in range(3, c, 2)]
Out[13]: [True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]

In [14]: all(c % p != 0 for p in range(3, c, 2))
Out[14]: True

And indeed 41 is a prime.

So prime_list returns a list of primes:

In [15]: prime_list(100)
Out[15]: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

To sum that up we simply use the sum() function:

In [16]: sum(prime_list(100))
Out[16]: 1061

Edit: Based on the comments, I tried the improvement that WillNess suggested and a real sieve using sets:

def prime_list(num):
    if num < 3:
        raise ValueError('this function only accepts arguments > 2')
    candidates = range(3, num+1, 2)
    L = [c for c in candidates if all(c % p != 0 for p in range(3, c, 2))]
    return [1, 2] + L

def prime_list2(num):
    if num < 3:
        raise ValueError('this function only accepts arguments > 2')
    candidates = range(3, num+1, 2)
    L = [c for c in candidates if all(c % p != 0 for p in
         range(3, int(math.sqrt(c))+1, 2))]
    return [1, 2] + L

def prime_list3(num):
    candidates = set(range(3, num+1, 2))
    results = [1, 2]
    while candidates:
        t = list(candidates)[0]
        results.append(t)
        candidates -= set(range(t, num+1, t))
    return results

Some timings for num=100:

In [8]: %timeit prime_list(100)
1000 loops, best of 3: 180 us per loop

In [9]: %timeit prime_list2(100)
1000 loops, best of 3: 192 us per loop

In [10]: %timeit prime_list3(100)
10000 loops, best of 3: 83.9 us per loop

And num=1000:

In [11]: %timeit prime_list(1000)
100 loops, best of 3: 8.05 ms per loop

In [12]: %timeit prime_list2(1000)
100 loops, best of 3: 2.43 ms per loop

In [13]: %timeit prime_list3(1000)
1000 loops, best of 3: 1.26 ms per loop

num = 5000:

In [14]: %timeit prime_list(5000)
1 loops, best of 3: 166 ms per loop

In [15]: %timeit prime_list2(5000)
100 loops, best of 3: 11.1 ms per loop

In [16]: %timeit prime_list3(5000)
100 loops, best of 3: 15.3 ms per loop

And finally num=50000:

In [18]: %timeit prime_list3(50000)
1 loops, best of 3: 1.49 s per loop

In [19]: %timeit prime_list2(50000)
1 loops, best of 3: 170 ms per loop