Euler项目#7 -10001素数

Question

我刚刚在Swift中完成了欧拉#7项目，而且由于在代码评审上还没有任何版本，我想对我为改进它所做的事情有一些评论。

通过列出前六个素数: 2，3，5，7，11和13，我们可以看到第6素数是13。10001素数是什么？

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)

代码在0.0181439518928528 s中执行。

Answer 1

func isPrime(number:Int) -> Bool { ... }

不需要测试if number < 9，因为这在一般的else案例中有涉及，而且我认为number <= 3比if number < 4更容易理解。

一个更普遍的问题是，函数应该如何处理零或负数。“素数”一词只为正整数定义，number参数在这个程序中肯定是正的。但是，对于其他Project挑战，您可以重用相同的函数作为一种库函数，然后对有效的参数进行合理的检查。有两种可能的方法：

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

区别在于(默认情况下) assert()只在Debug构建中签入，而不是在发布版构建中签入。除非将优化级别设置为precondition()，否则始终检查-Ofast。

还可以考虑将参数类型从Int更改为UInt。

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

函数名没有很好地选择。在Objective中，"get“前缀仅用于间接返回值的函数(比较“可可编码指南”)，我认为这个惯例也适用于Swift程序。此外，函数不返回“数字”，而是返回“素数”，参数prime: Int也不是素数。我会把它简单地改为

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

使用n = 1调用时，它返回1而不是2。同样，这与这个特定的程序无关，但是如果您想要在其他挑战中重用该函数，则应该修复它。

而不是局部计数变量

var xThPrime = prime - 1

还可以通过用var声明局部变量来修改它，但这取决于您是否认为它更易读。然后，该函数将如下所示：

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) { ... }

在回答您的另一个问题欧拉#8项目-系列中最大的产品时，我已经提出了一个建议，即更改计时函数，以便更好地重用代码。如果应用于这个问题，它看起来就像

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)

最后，一些可能的性能改进。您的程序足够快，足以解决Project问题。要找到更大的素数可能太慢了。在我的电脑上，你的方法

• 0.01 S找到10001素数，和
• 10.4 S去找1000位素数。

一个简单的改进是记住已经找到的素数，并将其作为数组传递给isPrime()函数，后者只会尝试除以素数：

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
}

现在我们有了

• 0.01 S找到10001素数，和
• 6 S去找1000位素数。

“埃拉托斯提尼筛”是一种快速查找大量素数的方法。然而，它需要更多的内存，您必须事先估计搜索的素数有多大。

以下是一个可能的实现：

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
}

这样做要快得多：

• 0.001 S找到10001素数，和
• 0.17 S找到了1000位素数。

Answer 2

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

我们可以在这里实现一些Swift语法：

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

不过，我不知道这在性能上会有什么比较。不过，我怀疑是一样的还是更好的。