这是悦乐书的第 190 次更新, 第 193 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 49 题 (顺位题号是 204). 计算小于非负数 n 的素数的数量. 例如:
输入: 10
输出: 4
说明: 有 4 个素数小于 10, 它们是 2,3,5,7.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 第一种解法
判断一个数 n 是否为素数, 就需要判断 1 到 n-1 之间的数能否被 n 整除, 能够被整除说明不是素数, 否则就是素数.
- public int countPrimes(int n) {
- if (n <= 2) {
- return 0;
- }
- int count = 0;
- for (int i=2;i<n; i++) {
- boolean flag = true;
- for (int j=2; j<i; j++) {
- if (i%j == 0) {
- flag = false;
- }
- }
- if (flag) {
- count++;
- }
- }
- return count;
- }
但是此解法的时间复杂度太高了, 是 O(n^2), 那就需要再优化下.
03 第二种解法
如果 n 可以被某个数 p 整除, 则 n = p*q, 并且由于 p≤q, 我们可以推导出 p 小于等于根号 n. 对正整数 n, 如果用 2 到根号 n 之间的所有整数去除, 均无法整除, 则 n 为质数. 对于根号的处理, 我们将内部循环换成指针的平方.
- public int countPrimes2(int n) {
- int count = 0;
- for (int i = 1; i < n; i++) {
- if (isPrime(i)) count++;
- }
- return count;
- }
- private boolean isPrime(int num) {
- if (num <= 1) return false;
- for (int i = 2; i * i <= num; i++) {
- if (num % i == 0) return false;
- }
- return true;
- }
04 第三种解法
一个素数的倍数都不是素数. 比如 2, 依次往上乘, 4,6,8 等等, 他们都不是质数, 再比如 3, 也可以依次往上乘, 得到的结果也不是质数.
我们从 2 开始遍历到根号 n, 先找到第一个质数 2, 然后将其所有的倍数全部标记出来, 然后到下一个质数 3, 标记其所有倍数, 一次类推, 直到根号 n, 此时数组中未被标记的数字就是质数. 对此我们需要使用一个长度为 n 的布尔类型数组, 来存储那些被标记的非质数. 外层循环和内层循环都是遍历到根号 n 即可.
- public int countPrimes3(int n) {
- boolean[] isPrime = new boolean[n];
- for (int i = 2; i < n; i++) {
- isPrime[i] = true;
- }
- for (int i = 2; i * i < n; i++) {
- if (!isPrime[i])
- continue;
- for (int j = i * i; j < n; j += i) {
- isPrime[j] = false;
- }
- }
- int count = 0;
- for (int i = 2; i < n; i++) {
- if (isPrime[i])
- count++;
- }
- return count;
- }
此解法的空间复杂度是 O(n), 时间复杂度是 O(nlog(log n)).
05 小结
算法专题目前已连续日更超过一个月, 算法题文章 49 + 篇, 公众号对话框回复 [数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/696d8d88a233