【英文题目】(学习英语的同时,更能理解题意哟~)
Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
【中文题目】
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
【思路】
第一种方法,暴力破解,遍历每个小于n的数,判断其是否为质数,时间复杂度太高。
第二种方法,使用数组。给每个数一个标签True(0和1的标签为False),遍历数组时,若标签为True,表明该数是质数,将其倍数全部标记为False(相当于改变了所有非质数的标签)。最后统计True的个数即可。循环时,i*i<=n时,不用再继续遍历,因为所有非质数的标签已经更改。
【代码】
python版本
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
ls = [True] * n
if n < :
return
ls[] = ls[] = False
for i in range(, int(n ** 0.5)+):
if ls[i] == False:
continue
for j in range( * i, n, i):
ls[j] = False
return sum(ls)
C++版本
class Solution {
public:
int countPrimes(int n) {
vector<int> ls(n, );
if(n < )
return ;
ls[] = , ls[] = ;
for(int i=; i * i <= n; i++){
if(ls[i] == )
continue;
for(int j=*i; j < n; j=j+i)
ls[j] = ;
}
int sum = ;
for(int i=; i<n; i++)
sum += ls[i];
return sum;
}
};
给我好看