怎么判断一个整数是否是素数？

什么是素数？

• 一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数
• 0 和 1 既不是质数也不是合数，最小的质数是 2

判断一个整数是否是素数，我们会三种常见方法。

最简单的方法

func checkPrime(_ num: Int) -> Bool {
    guard num > 3 else { return num > 1 }
    
    for i in 2...(num-1) {
        if num % i == 0 {
            return false
        }
    }
    return true
}

优化方法一

func checkPrime(_ num: Int) -> Bool {
    guard num > 3 else { return num > 1 }

    for i in 2...(num / 2) {
        if num % i == 0 {
            return false
        }
    }
    return true
}

假设 n 是一个素数，那么它可能的最小整除约数是 2，而可能的最大整除约数是 n/2。

所以我们可以得到结论：如果一个数 n 是素数，那么在 (2...n/2) 之间一定有一个可以被其整除的数。

优化方法二

func checkPrime(_ num: Int) -> Bool {
    guard num > 3 else { return num > 1 }

    for i in 2...Int(sqrt(Double(num))) {
        if num % i == 0 {
            return false
        }
    }
    return true
}

假设 n 是一个素数，则肯定存在 n = a * b（a 和 b 不能是 1 或者 n）。我们又知道 n = sqrt(n) * sqart(n)。所以 a 和 b 只有两种可能：

• a 和 b 都等于 sqrt(n)
• a 和 b 一个大于 sqrt(n)，另一个小于 sqrt(n)

所以我们可以得到结论：如果一个数 n 是素数，那么在 (2...sqrt(n)) 之间一定有一个可以被其整除的数。