CodeEval Sum of Primes

The CodeEval problem #4 is similar to the previous one. Again prime numbers, this time we have to get the first one thousand of them, and return their sum.

No need for a test case, we have just a single possible outcome, and it should be 3682913.

We need a generic function to check if a number is prime, I implemented it in this way:
primes = [2, 3]  # 1

def is_prime(value):
    for prime in primes:
        if prime ** 2 > value:  # 2
        elif i % prime == 0:  # 3
            return False
    return True
1. In this list I am going to store the prime numbers. It make sense to store them somewhere instead of simply checking if a number is prime and then increase a counter, because we also rely on this list to see if a candidate is prime or not.
2. Extra condition to interrupt the for loop. We stop checking at the square root of the candidate. Or, other way round, cheaper to calculate, when the square of the current prime is bigger than the candidate.
3. If we find a divisor for the candidate, it is not a prime number.

And here is the body of my python script:
while len(primes) < 1000:  # 1
    for i in count(primes[-1] + 2, 2):  # 2
        if is_prime(i):  # 3
1. I won't stop calculating until I have one thousand primes.
2. I start looking from the next prime from the last one stored in the list, increased by two. And then I go on, stepping by two. This is because I am not interested in even numbers, evidently not prime. I use the itertool count() function because I don't have a (theoric) end in this loop, and the built-in range() would require a dummy end to work, making the code a tad less clear.
3. When I find the next prime, I push it to the list, break the for loop, and go on to the next iteration in the when loop.

Then I just have to print the sum of all the primes.
For a complete reference, I have pushed my python script to GitHub.

No comments:

Post a Comment