# Euler Solution 10

### From ProgSoc Wiki

## Contents |

# 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; }

## Haskell by SanguineV

Runtime: 12s

{- Create a lazy list of prime numbers. - Start with 2 and 3 as known primes. - 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)