文档章节

LeetCode:Count Primes - 统计质数数量

北风其凉
 北风其凉
发布于 2015/09/06 23:31
字数 478
阅读 835
收藏 4

1、题目名称

Count Primes(统计质数数量)

2、题目地址

https://leetcode.com/problems/count-primes/

3、题目内容

英文:Count the number of prime numbers less than a non-negative number, n.

中文:统计正整数n以内(不含n本身)质数的数量

4、一个TLE的方法

从1到n,考察每个数字是否为质数。这个方法由于花费时间较长,不能满足题目中对时间的要求。

一段实现此方法的Java代码如下:

/**
 * 功能说明:LeetCode 204 - Count Primes
 * 开发人员:Tsybius2014
 * 开发时间:2015年9月6日
 */
public class Solution {
    
    /**
     * 计算n以下的质数数量
     * @param n 正整数
     * @return n以下的质数数量
     */
    public int countPrimes(int n) {
        
        if (n <= 1) {
            return 0;
        }
        
        int result = 0;
        boolean isPrime = true;
        for (int i = 2; i < n; i++) {

            //判断数字i是否为质数
            isPrime = true;
            if (i == 2 || i == 3 || i == 5 || i == 7) {
                isPrime = true;
            } else if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0) {
                isPrime = false;
            } else {
                for (int j = 2; j <= Math.sqrt(i); j++) {
                    if (i % j == 0) {
                        isPrime = false;
                        break;
                    }
                }
            }
            
            //如果i是质数result自增1
            if (isPrime) {
                result++;
            }
        }
        
        return result;
    }
}

4、解题方法

另一个求质数的方法是埃拉托斯特尼筛法(Sieve of Eratosthenes),这个方法需要声明一个非常大的数组,但速度较上面的方法要快很多。

一段实现此方法的Java代码如下:

/**
 * 功能说明:LeetCode 204 - Count Primes
 * 开发人员:Tsybius2014
 * 开发时间:2015年9月6日
 */
public class Solution {
    
    /**
     * 计算n以下的质数数量
     * @param n 正整数
     * @return n以下的质数数量
     */
    public int countPrimes(int n) {
        
        if (n <= 1) {
            return 0;
        }

        int result = 0;
        boolean[] arr = new boolean[n];
        for (int i = 2; i < n; i++) {
            
            //如果arr[i]是质数则将其倍数全部标记为合数,否则不予考虑
            if (!arr[i]) {
                result++;
            } else {
                continue;
            }

            int j = 2;
            while (i * j < n) {
                arr[i * j] = true;
                j++;
            }
        }
        
        return result;
    }
}

END

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 118
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
python leetcode-204 Count Primes 质数计数

title: "leetcode-204 Count Primes 质数计数" 我的博客 https://zszdata.com/2019/03/09/count-primes/ Count Primes Count the number of prime numbers less than a non-negative number,......

sz88888
04/08
0
0
LeetCode算法题-Count Primes(Java实现)

这是悦乐书的第190次更新,第193篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第49题(顺位题号是204)。计算小于非负数n的素数的数量。例如: 输入:10 输出:4 说明:有4...

小川94
2018/12/03
0
0
求质数的各种算法

首先声明本人水平有限,仅仅做一下记录,有错的地方请指正,文章垃圾请包容!! 在网上不小心浏览到一篇技术博客,叫做《求质数算法的N种境界(N>10)》,写得很好,有兴趣的读者自己去搜索。...

勤奋的人生
2017/04/23
0
0
Leetcode 204. Count Primes

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 Version 2 Reference https://leetcode.com/problems/count-primes/description/......

SnailTyan
2018/08/17
0
0
204. Count Primes - LeetCode

Queston 204. Count Primes Solution 题目大意:给一个数,求小于这个数的素数的个数 思路:初始化一个boolean数组,初始设置为true,先遍历将2的倍数设置为false,再遍历3并将3的倍数置为fal...

yysue
2018/07/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周一乱弹 —— 加油,还有11个小时就下班了

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @_全村的希望 :吴亦凡把大碗面正儿八经做成单曲了,你别说,还挺好听 《大碗宽面》- 吴亦凡 手机党少年们想听歌,请使劲儿戳(这里) @tom_t...

小小编辑
29分钟前
74
8
C++ vector和list的区别

1.vector数据结构 vector和数组类似,拥有一段连续的内存空间,并且起始地址不变。 因此能高效的进行随机存取,时间复杂度为o(1); 但因为内存空间是连续的,所以在进行插入和删除操作时,会造...

shzwork
今天
6
0
Spring之invokeBeanFactoryPostProcessors详解

Spring的refresh的invokeBeanFactoryPostProcessors,就是调用所有注册的、原始的BeanFactoryPostProcessor。 相关源码 public static void invokeBeanFactoryPostProcessors(Configu......

cregu
昨天
5
0
ibmcom/db2express-c_docker官方使用文档

(DEPRECIATED) Please check DB2 Developer-C Edition for the replacement. What is IBM DB2 Express-C ? ``IBM DB2 Express-C``` is the no-charge community edition of DB2 server, a si......

BG2KNT
昨天
4
0
Ubuntu 18.04.2 LTS nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic)

平台:Ubuntu 18.04.2 LTS nvidia-docker2 版本:2.0.3 错误描述:在安装nvidia-docker2的时候报dpkg依赖错误 nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic) 先看一下依......

Pulsar-V
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部