204.计算质数

一、题目原型：

统计所有小于非负整数 n 的质数的数量。

二、示例剖析：

输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。（不包括10）

三、解题思路：

注意：题意是 所有小于n的数字里，
质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
也就是只能被1和自己整除的数。

首先看一个关于质数分布的规律：大于等于5的质数一定和6的倍数相邻。例如 （5和7）（11和13）（17和19）等等；
证明：令x≥1，将大于等于5的自然数表示如下：
··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ···
可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。
因此在5到sqrt(n)中每6个数只判断2个，时间复杂度O(sqrt(n)/3)。

// 判断一个数字是否为质数
func isPrime(_ num: Int) -> Bool {
    
    if num%6 != 1 && num%6 != 5 { //不是质数
        return false
    }
    
    let num_sqrt = sqrt(Double(num))
    let n = Int(num_sqrt) + 1
    
    var index: Int = 5
    
    if n >= 5 {
        while index <= n {
            if num % index == 0 || num % (index+2) == 0 { //不是质数
                return false
            }
            index = index + 6
        }
    }
    return true
}

#func countPrimes(_ n: Int) -> Int {
    var count: Int = 0
    if n == 1 || n == 2 {
        return 0
    }else if n == 3 {
        return 1
    }else if n == 4 || n == 5 {
        return 2
    }else if n == 6 || n == 7 {
        return 3
    }else if n > 7 {
        for i in 7..<n {
            count = 3
            if self.isPrime(i) {
                count = count + 1
            }
        }
    }
    return count
}

四、小结

耗时1524毫秒，超过45.16%的提交记录，总提交数20。