LeetCode.jpg
题目：计数质数
描述：统计所有小于非负整数 n 的质数的数量。
案例1：
代码语言：javascript复制输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。质数的定义：质数
方案一：判断质数
代码一：
代码语言：javascript复制func countPrimes(_ n: Int) -> Int {
if n < 3 {
return 0
}
var count = 1
//判断大于3的奇数
for i in 3..<n where i % 2 != 0 {
if isPrime(i) {
print(i)
count = 1
}
}
return count
}
func isPrime(_ n: Int) -> Bool {
//为了下面的for循环能正常进行，在这里加这个判断，只有3不满足下面循环条件
if n == 3 {
return true
}
//对N开根号
for i in 2...Int(sqrt(Double(n))) {
if n % i == 0 {
return false
}
}
return true
}执行用时：4812ms、、、真是慢啊，要是上面条件直接是n或者n/2提交直接超时
方案二：筛法
代码二：
代码语言：javascript复制func countPrimes(_ n: Int) -> Int {
if n < 3 {
return 0
}
if n == 3 {
return 1
}
var array = [Bool](repeating: true, count: n)
for i in 2...Int(sqrt(Double(n))) {
if i * i >= n { break }
if !array[i] { continue }
var j = i * i
while j < n {
array[j] = false
j = j i
}
}
var count = 0
for i in 2..<n {
if array[i] {
count = 1
}
}
return count
}执行用时：420ms
