Fork me on GitHub

leetcode之204. 计数质数

发表于 | 分类于
字数统计 240 字 | 阅读时长 1 分钟

题目描述：

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

示例:

1
2
3
4
> 输入: 10
> 输出: 4
> 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
>

解题思路：

素数要出现只可能出现在6x的相邻两侧

时间复杂度：$O(n^2)$, 空间复杂度:$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
	public:
		int countPrimes(int n) {

			int count = 0;
			if(n <= 2) return count;
			count += 1;
  			// 每次只需要计算奇数就可以了
			for(int i = 3; i < n;i += 2)
			{
				if(isPrime(i)) count++;
			}

			return count;
		}

		bool isPrime( int num )
		{
  			//两个较小数另外处理
			if(num == 2 || num ==3 )
				return true;
 			//不在6的倍数两侧的一定不是质数
			if(num %6 != 1 && num %6 != 5)
				return false;
			int tmp = sqrt( num);
 			//在6的倍数两侧的也可能不是质数
			for(int i = 5; i <= tmp; i += 6 )
				if(num % i == 0 || num %(i + 2) == 0 )
					return false;
  				//排除所有，剩余的是质数
				return true ;
			};
};