[LeetCode] 204. Count Primes

cheukyin 发布于2019-08-16 13:38 / 1949人阅读

Problem

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.

Solution

class Solution {
    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                count++;
                for (int j = 2; j*i < n; j++) {
                    notPrime[i*j] = true;
                }
            }
        }
        return count;
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72067.html

204. Count Primes

摘要：题目链接思路首先要知道如何判断一个数字是否为素数。具体方法可以看这里其次，如果朴素的判断，那么会因为效率底下而超时。所以在我们每次找到素数的时候，可以把素数的倍数都标记为非素数。这样可以节省轮询的时间。算法复杂度时间空间代码题目链接：Counting Primes 思路：首先要知道如何判断一个数字是否为素数。具体方法可以看这里其次，如果朴素的判断，那么会因为效率底下而超时。所以在我...

王笑朝 2019-07-30 16:58 评论0 收藏0
[Leetcode] Count Primes 数素数

摘要：利用这个性质，我们可以建立一个素数数组，从开始将素数的倍数都标注为不是素数。第一轮将等表为非素数，然后遍历到，发现没有被标记为非素数，则将等标记为非素数，一直到为止，再数一遍素数数组中有多少素数。代码将的倍倍倍都标记为非素数 Count Primes Description: Count the number of prime numbers less than a non-nega...

Achilles 2019-08-14 12:28 评论0 收藏0
leetcode部分题目答案之JavaScript版

摘要：自己没事刷的一些的题目，若有更好的解法，希望能够一起探讨项目地址自己没事刷的一些LeetCode的题目，若有更好的解法，希望能够一起探讨 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...

alphahans 2019-08-21 16:20 评论0 收藏0
[LeetCode] Count Primes

摘要：用数组标记非质数，每当出现一个为，计数器加一。关于质数有三点大于的质数一定是奇数，如，，奇数中的非质数也一定是奇数的乘积。首先，我们用从到进行标记。标记完所有的合数之后，再用到之间的遍历，所有未被标记的质数。 Problem Count the number of prime numbers less than a non-negative number, n. Note 用数组fla...

Shisui 2019-08-14 15:54 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0