Euler Solution 10

From ProgSoc Wiki

Jump to: navigation, search

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)
Personal tools