Project Euler #10 in Swift - Summation of primes

Question

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.

Answer 1

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.

• Mehdi.Sqalli: 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
• thepace: 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.
• Mehdi.Sqalli: 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.
• thepace: My mistake. Sincere apologies. Will correct and generalise it as far as possible.