7
\$\begingroup\$

I just finished Project Euler #7 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.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

import Foundation

func isPrime(number:Int) -> Bool {

    if number == 1 {
        return false
    }
    else if number < 4 {
        return true
    }
    else if number % 2 == 0 {
        return false
    }
    else if number < 9 {
        return true
    }
    else if number % 3 == 0 {
        return false
    }
    else {
        let maxPrime = Int(ceil(sqrt(Double(number))))

        for var i = 5; i <= maxPrime; i += 6 {
            if number % i == 0  || number % (i + 2) == 0 {
                return false
            }
        }
    }

    return true
}

func getNumberForXthPrime(prime:Int) -> Int {

    var xThPrime = prime - 1 // We skip the prime 2 with the += 2
    var number = 1

    while xThPrime > 0 {

        number += 2
        if isPrime(number) {
            xThPrime--
        }
    }

    return number
}

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

printTimeElapsedWhenRunningCode(getNumberForXthPrime)

The code executes in 0.0181439518928528 s.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to Code Review! I added the Euler problem description and a link to the problem for you. I hope you get some good reviews! \$\endgroup\$ – Phrancis Dec 23 '14 at 17:02
  • \$\begingroup\$ Is the goal here performance or readability? \$\endgroup\$ – nhgrif Dec 24 '14 at 2:09
  • \$\begingroup\$ Performance and/or readability. Anything you want to point out. \$\endgroup\$ – Mehdi.Sqalli Dec 24 '14 at 13:58
5
\$\begingroup\$
func isPrime(number:Int) -> Bool { ... }

The test if number < 9 is not needed because that is covered by the general else case, and I think that number <= 3 is easier to understand than if number < 4.

A more general question is how the function should deal with zero or negative arguments. The term "prime number" is only defined for positive integers, and the number argument is certainly positive in this program. But you might reuse the same function for other Project Euler challenges as a kind of library function and then it makes sense check for a valid argument. There are two possible methods:

assert(number > 0, "argument must be positive")
precondition(number > 0, "argument must be positive")

The difference is that (by default) assert() is only checked in the Debug build, but not in Release build. precondition() is checked always unless you set the optimization level to -Ofast.

You might also consider to change the argument type from Int to UInt.


func getNumberForXthPrime(prime:Int) -> Int { ... }

The function name is not well chosen. In Objective-C, the "get" prefix is used only for functions that return a value indirectly (compare "Coding Guidelines for Cocoa") and I think this convention applies to Swift programs as well. Also the function does not return a "number" but a "prime", and the argument prime: Int is not a prime. I would change that simply to

func nthPrime(n : Int) -> Int { ... }

When called with n = 1, it returns 1 and not 2. Again, this is not relevant in this particular program, but you should fix it if you want to reuse the function for other challenges.

Instead of a local counting variable

var xThPrime = prime - 1

you can also modify the local parameter variable by declaring it with var, but that is up to you to decide if you find it more readable or not. The function would then look like this:

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

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

    if n == 1 {
        return 2
    }

    var number = 3
    n -= 2 // 3 is the second prime

    while n > 0 {
        number += 2
        if isPrime(number) {
            n--
        }
    }

    return number
}

func printTimeElapsedWhenRunningCode(operation:(xThPrime:Int) -> Int) { ... }

I already made a suggestion in my answer to your other question Project Euler #8 - Largest product in a series to change the timing function for better code reuse. Applied to this problem, it would look like

func euler7() {
    let result = nthPrime(10_001)
    println(result)
}

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

printTimeElapsedWhenRunningCode(euler7)

Finally, some possible performance improvements. Your program is fast enough for the Project Euler Problem. It might be too slow to find larger prime numbers. On my computer, your method takes

  • 0.01 s to find the 10 001st prime number, and
  • 10.4 s to find the 1 000 000st prime number.

A simple improvement would be to remember the primes that were already found and pass that as an array to the isPrime() function which then would only try to divide by prime numbers:

func isPrime(number:Int, primes: [Int]) -> Bool {

    let maxPrime = Int(ceil(sqrt(Double(number))))
    for prime in primes {
        if prime > maxPrime {
            break
        }
        if number % prime == 0 {
            return false
        }
    }
    return true
}

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

    var primes = [2, 3]

    if n <= primes.count {
        return primes[n-1]
    }

    var number = primes.last!
    n -= primes.count

    while n > 0 {
        number += 2
        if isPrime(number, primes) {
            primes.append(number)
            n--
        }
    }

    return number
}

Now we have

  • 0.01 s to find the 10 001st prime number, and
  • 6 s to find the 1 000 000st prime number.

The "Sieve of Eratosthenes" is a very fast method to find a large number of primes. However, it requires more memory, and you have to estimate in advance how large the searched prime will be.

Here is a possible implementation:

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

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

    // The below estimate is only valid for n > 6:
    if n <= 6 {
        return [2, 3, 5, 7, 11, 13][n-1]
    }

    // Upper bound from http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number:
    let d = Double(n)
    let upperBound = Int(d * (log(d) + log(log(d))))

    var composite = [Bool](count: upperBound + 1, repeatedValue: false)
    var x = 2
    let maxPrime = Int(ceil(sqrt(Double(upperBound))))

    while x <= maxPrime {
        if !composite[x] {
            if (--n == 0) {
                return x
            }
            for var y = x*x; y <= upperBound; y += x {
                composite[y] = true
            }
        }
        x++
    }
    while x <= upperBound {
        if !composite[x] {
            if (--n == 0) {
                return x
            }
        }
        x++
    }

    assertionFailure("Fatal error")
    return -1
}

This is considerably faster:

  • 0.001 s to find the 10 001st prime number, and
  • 0.17 s to find the 1 000 000st prime number.
\$\endgroup\$
  • \$\begingroup\$ Really nice review! I Learned a lot. Just to complete it, you should add assert(n > 0, "argument must be positive") in the nthPrime using the sieve. Or a precondition. \$\endgroup\$ – Mehdi.Sqalli Dec 26 '14 at 12:12
  • \$\begingroup\$ @Mehdi.Sqalli: You are welcome! – Done. – Waiting for PE #10 :) \$\endgroup\$ – Martin R Dec 26 '14 at 12:30
5
\$\begingroup\$
for var i = 5; i <= maxPrime; i += 6 {
    if number % i == 0  || number % (i + 2) == 0 {
        return false
    }
}

We can implement some Swift syntax here:

for i in stride(from:5 through:maxPrime by: 6) {
    if number % i == 0 || number % (i + 2) == 0 {
        return false
    }
}

I don't know how this would compare in terms of performance however. I suspect it's the same or better however.

\$\endgroup\$
  • \$\begingroup\$ It is kind of weird. It's actually 10 times slower. It goes from 0.018s to 0.18s, which is odd... Anyone knows why ? \$\endgroup\$ – Mehdi.Sqalli Dec 24 '14 at 14:30
  • \$\begingroup\$ @Mehdi.Sqalli: In my test, stride() is much slower in Debug mode (0.17 vs 0.02 seconds), but only slightly slower in Release mode (0.01 vs 0.009 s). \$\endgroup\$ – Martin R Dec 25 '14 at 17:22
  • \$\begingroup\$ Yep I was in Debug mode. It is slightly slower in Release mode though... \$\endgroup\$ – Mehdi.Sqalli Dec 26 '14 at 12:14

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.