HiveBrain v1.2.0
Get Started
← Back to all entries
patternswiftMinor

Project Euler #10 in Swift - Summation of primes

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
swiftprimesprojecteulersummation

Problem

I just finished Project Euler #10 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it.

I hope I learned some from the previous code reviews :).


The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.


Find the sum of all the primes below two million.

import Foundation

func summationOfPrimesBelow(var n:Int) -> Int {

    assert(n > 0, "argument must be positive")

    var composite = [Bool](count: n, repeatedValue: false)

    var x = 2
    let maxPrime = Int(ceil(sqrt(Double(n))))

    while x  ()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    println("Time elapsed : \(timeElapsed) s")
}

printTimeElapsedWhenRunningCode(euler10)


The code executes in 0.012s in Release mode.

Solution

Since we know that primes can be represented by 6x+1 or 6x-1 except for 2,3, we could skip them as follows:

//Handle explicitly for n<5 i.e for n = 0,1,2,3,4 and proceed otherwise.
if n<3 { // n=0,1,2
    return 0
}
if n<5 {// n = 3,4
    return (n==3)?2:5
}

var x = 5
while x <= maxPrime {
    if composite[x] == false {
        for y in stride(from: x * x, through: n - 1, by: x) {
            composite[y] = true
        }
    }
    x+=2 
    if x<n && composite[x] == false {
        for y in stride(from: x * x, through: n - 1, by: x) {
            composite[y] = true
        }
    }
    x+=4
}

var result = 5 // 2 + 3
for i in stride(from: 5, through: composite.count - 1, by: 4) {
    if composite[i] == false {
        result += i
    }
    i+=2
    if i<n && composite[i] == false {
        result += i
    }
}


Results: With your code it took me 33ms with mine its down to 23ms.

Code Snippets

//Handle explicitly for n<5 i.e for n = 0,1,2,3,4 and proceed otherwise.
if n<3 { // n=0,1,2
    return 0
}
if n<5 {// n = 3,4
    return (n==3)?2:5
}

var x = 5
while x <= maxPrime {
    if composite[x] == false {
        for y in stride(from: x * x, through: n - 1, by: x) {
            composite[y] = true
        }
    }
    x+=2 
    if x<n && composite[x] == false {
        for y in stride(from: x * x, through: n - 1, by: x) {
            composite[y] = true
        }
    }
    x+=4
}

var result = 5 // 2 + 3
for i in stride(from: 5, through: composite.count - 1, by: 4) {
    if composite[i] == false {
        result += i
    }
    i+=2
    if i<n && composite[i] == false {
        result += i
    }
}

Context

StackExchange Code Review Q#74923, answer score: 2

Revisions (0)

No revisions yet.