06.03.08
Project Euler: 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?
05.30.08
Project Euler: Problem 7
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
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))
n = 10001
count_of_found = 2 # assuming 2 and 3 to start
current_number = 3
current_prime = 3
while count_of_found < n:
current_number += 2
if isPrime(current_number):
current_prime = current_number
count_of_found += 1
print 'nth prime for n=%d is %s' % (n, current_prime)
This problem was originally solved with a factorize function written for a previous problem, checking primality by looking at the number of factors. This way is faster. Plus, it’s good “generator expression” practice. :)
