patternswiftMinor
Project Euler #10 in Swift - Summation of primes
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.
The code executes in 0.012s in Release mode.
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:
Results: With your code it took me 33ms with mine its down to 23ms.
//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.