06.03.08

Project Euler: Problem 10

Posted in python tagged , , , at 4:26 pm by redochre

Problem 10:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

A solution:

import math

def isPrime(num):
    if type(num) != int: return False
    if num == 2: return True
    if num < 2 or num % 2 == 0: return False
    return not any(num % i == 0 for i in range(3, int(math.sqrt(num))+1, 2))

sum = 0
for i in range(2,2000000):
    if isPrime(i): sum += i

print sum

Straightforward, yes?

2 Comments »

  1. Kadhirvel said,

    29 July, 2008 at 10:55 am

    Please follow the link below for fact about primes

    http://kadiprimality.blogspot.com/

  2. Dan Turner said,

    22 July, 2009 at 2:14 am

    Thought I’d let you know that this is a lovely problem that can be solved with one line of Python. :-D

    [Code]
    print sum([x for x in xrange(1,2000000,2) if (not (x < 2 or any(x % y == 0 for y in xrange(2, int(x**0.5) + 1))))])+2
    [/Code]

    The extra plus-two is because the for loop skips all even numbers.

    Also note that to test for primality of n, you need only test up to sqrt(n), since any factor below the square root has a corresponding one above, with the exception of square numbers. This is why I have int(x**0.5) + 1.

    :-)


Leave a Comment