# Solutions for Problem 10

Find the sum of all prime numbers less than 2 million.

## C++ by ctd

Runtime: 2.3s

```#include <cstdlib>
#include <iostream>
#include <cmath>
#define MAXIMUM_NUMBER 2000000

using namespace std;

bool isPrime (unsigned int);

int main ()
{
unsigned long long sum = 0;
for (unsigned int i = 2; i < MAXIMUM_NUMBER; i++) {
if (isPrime (i))
sum += i;
}
cout << "Sum of primes: " << sum << endl;

return EXIT_SUCCESS;
}

bool isPrime (unsigned int i)
{
if (i <= 1) return false;
unsigned int upper = sqrt (i) + 1;
for (unsigned int lower = 2; lower < upper; lower++) {
if (i % lower == 0)
return false;
}
return true;
}
```

Runtime: 12s

```{- Create a lazy list of prime numbers.
- After this generate primes using a prime wheel, selecting candidate
- primes of the form:
- 6*k + 1 or 6*k + 5
- Is more efficient by only checking these candidates.
-}
primes :: [Integer]
primes = 2:3:primes'
where
1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
primes'        = p : filter isPrime candidates
isPrime n       = all (not . divides n) \$ takeWhile (\p -> p*p <= n) primes'
divides n p     = n `mod` p == 0

{- Add up the elements of the primes list, taking elements until they exceed 2 million -}
main = print (foldl (+) 0 (takeWhile (< 2000000) primes))
```

## Python by Althalus

Runtime: 88 Seconds

```import time, math
start_time = time.time()

#Stole this idea from the comments in one of Thomas's Haskell programs.
#Generate a list of primes starting with 2,3,5 and finding the others
#by 6*k+1, 6*k+5 (then check them)

#Either my approach isn't as efficient, or Python doesn't do it as well as Haskell.
primes = [2,3,5]

def getPrime(k,r):
number = 6*k+r
for i in range(2,int(math.sqrt(number))+1):
if number%i == 0:
return None
return number

for i in range(1,333333):#6*333333 = 2mil (or just under)
number = getPrime(i,1)
if number != None:
primes.append(number)
number = getPrime(i,5)
if number != None:
primes.append(number)

total = 0
for prime in primes:
total += prime

print (total)
run_time = time.time() - start_time
print(run_time)

#### This was my first approach. Took a looooong time.
##Find sum of all primes less than 2 mil
#
##The first prime is 2, but 2 is the only even prime.
##If we start counting on an odd number, we can increment by 2,
##and skip all even numbers.
##We just need to start our total at 2, to allow for our first prime.
#number=1    #Although number starts at 1, it gets incremented soon as the
#            #prgram enters the list. First actually checked is 3.
#count=2
#
#while number < 2000000:
#	number+=2 #an even number won't be prime
#	prime = True
#	i=2
#	while i <= math.sqrt(number)+1:
#		if number%i == 0:
#			prime=False
#			break
#		i+=1
#	if prime: count+=number
#
#print(count)
#run_time = time.time() - start_time
#print(run_time)
```