6
\$\begingroup\$

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 <= maxPrime {
        if composite[x] == false {
            for y in stride(from: x * x, through: n - 1, by: x) {
                composite[y] = true
            }
        }
        x++
    }

    var result = 0
    for i in stride(from: 2, through: composite.count - 1, by: 1) {
        if composite[i] == false {
            result += i
        }
    }

    return result
}

func euler10() {
    let number = summationOfPrimesBelow(2_000_000)

    println(number)
}

func printTimeElapsedWhenRunningCode(operation:() -> ()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    println("Time elapsed : \(timeElapsed) s")
}

printTimeElapsedWhenRunningCode(euler10)

The code executes in 0.012s in Release mode.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It is faster, thanks. The code does not work though for the values 1, 2, 3, and 6 : it returns 5 instead of 0, 1, 2 and 10. It crashes with 7. And you should replace for i in stride(from: 5, through: composite.count - 1, by: 4) { with for var i = 5; i < composite.count - 1; i += 4 { Otherwise you cannot use i += 2 in the loop \$\endgroup\$ – Mehdi.Sqalli Dec 28 '14 at 11:29
  • \$\begingroup\$ For <4, we need to handle it explicitly. For 6, we would get 10. composite[5] = false. So result = 5 + 5 = 10. For 7 it wouldn't crash. Could you recheck ? For <2, it should be 0. \$\endgroup\$ – thepace Dec 29 '14 at 4:27
  • \$\begingroup\$ I did test to write my comment. 6 gives back 5 as a result instead of 10. And 7 crashes. You should also edit your stride loop. \$\endgroup\$ – Mehdi.Sqalli Dec 29 '14 at 9:56
  • \$\begingroup\$ My mistake. Sincere apologies. Will correct and generalise it as far as possible. \$\endgroup\$ – thepace Dec 29 '14 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.