判断一个整数是否为素数

问题：给定一个正整数，如何判断它是否为素数？

  素数，又称之为质数，是指在大于1的自然数中，除了1和它本身以外不再有其他因数，这样的数被称为素数。

func challenge(number: Int) -> Bool {
    
    // 只有当输入的整数是大于等于2时，题目才有意义
    guard number >= 2 else { return false }
    
    // 遍历从[2, number)之间所有的正整数
    for i in 2 ..< number {
        
        // 如果number能被i整除
        if number % i == 0 {
            
            // 就说明number不是素数，返回false
            return false
        }
    }
    
    // 说明number是素数，返回true
    return true
}

  上面的算法肯定是对的，但是它还不够完美。我们都知道，自然界中的素数有无穷个，当一个数接近无穷大时，你可能要把从2到接近正无穷大的正整数都除以一遍，这个耗时将是难以忍受的。因此，我们要改进上面的算法。

  我们可以这样考虑：假设一个正整数n不是素数，那么肯定存在这样两个正整数x和y，使得n = x * y成立。再假设x和y都大于n的平方根，那么x * y > n肯定是成立的，但实际上这又是不可能的。所以，我们可以确定，x和y中至少有一个数，它是小于或者等于n的平方根的。

  上面这个结论有没有卵用呢？当然是有的，我们可以利用它大幅减少计算步骤。以素数143为例，它开平方然后向上取整，得到整数12，假设143不是素数的话，利用上面的结论可知，它肯定存在一个因子是小于或者等于12的，所以我们只需要在[2, 12)这个区间去搜索结果就可以了。用代码表示为：

func challenge1(number: Int) -> Bool {
    
    guard number >= 2 else { return false }
    
    // 把整数2排除
    guard number != 2 else { return true }
    
    // ceil(_: )向上取整，sqrt(_: )返回非负的平方根
    let max = Int(ceil(sqrt(Double(number))))
    
    // 除数只需要从2取到max就可以了
    for i in 2 ... max {
        
        // 如果能被i整除
        if number % i == 0 {
            
            // 则说明它不是素数，直接返回false
            return false
        }
    }
    return true
}

  这个方案和第一个比较起来，已经大幅减少了计算开销，是一个比较合理的算法。代码中用到了两个C语言标准库函数ceil(_: )和sqrt(_: )，它们分别表示向上取整函数和开平方根函数。