统计所有小于非负整数 n 的质数的数量。
名次解释:
质数:质数是指大于1的自然数中,除了1和它本身以外不再有其他因数的自然数.
提示：
0 <= n <= 5 * 106
摘一个示例做个说明.
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
条件分析:
- 统计所有小于n的质数的个数 -> 是要进行计数
- 非负整数 n -> n为0或者正整数,可能为0或1.0或1都不是质数
- 0 <= n <= 5 * 106 -> 老老实实计算吧,不要想着map解决问题
解决思路1:
- 根据分析1,采用累计计算,因为是统计一个n内所有的,也就是每个小于n的都要计算,所以采用循环
- 根据分析2,对0或1做特殊处理,直接返回比较快.
- 需要判断n以内的每个数是不是质数
因为是小于n的统计,所以当n小于3时,直接0、1、2的时候可以直接返回0.然后判断每一个是否是质数.累计相加即可,但是结果也是显而易见的.值太大的时候,直接超时了.
func countPrimes(_ n: Int) -> Int {
var count = 0
if n == 0 || n == 1 || n == 2{
return count
}
for i in 2 ..< n {
count += isPrimes(i)
}
return count
}
func isPrimes(_ n: Int) -> Int {
for i in 2 ..< n {
if n % i == 0 {
return 0
}
}
return 1
}
解决思路2:分析同思路1
1.优化点,从头开始判断的时候,如果不是质数,则相应的它的倍数也不会是质数.相应的倍数的倍数,直到大于n前都不会是质数.
定义一个长度为n的临时存储数据.然后循环判断小于n的数.如果存储的该数是质数则将该数字进行翻倍处理.直到结束.最后循环临时变量即可.
func countPrimes(_ n: Int) -> Int {
if n < 3 {
return 0
}
var count: Int = 0
var isPrimes = [Bool](repeating: true, count: n)
for index in 2 ..< n {
if isPrimes[index] {
var i = 2*index
while i < n {
isPrimes[i] = false
i += index
}
}
}
for index in 2 ..< n {
if isPrimes[index] {
count += 1
}
}
return count
}
测试用例:
let n = 0
let n = 1
let n = 2
let n = 3
let n = 10
let n = 100000
let n = 900000
考察要点:
- 数组
- 数学
- 枚举
- 数论
