[Leetcode] Count Primes 数素数

Achilles 发布于2019-08-14 12:28 / 1582人阅读

摘要：利用这个性质，我们可以建立一个素数数组，从开始将素数的倍数都标注为不是素数。第一轮将等表为非素数，然后遍历到，发现没有被标记为非素数，则将等标记为非素数，一直到为止，再数一遍素数数组中有多少素数。代码将的倍倍倍都标记为非素数

Count Primes

Description:

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

埃拉托斯特尼筛法 Sieve of Eratosthenes 复杂度

时间 O(NloglogN) 空间 O(N)

思路

如果一个数是另一个数的倍数，那这个数肯定不是素数。利用这个性质，我们可以建立一个素数数组，从2开始将素数的倍数都标注为不是素数。第一轮将4、6、8等表为非素数，然后遍历到3，发现3没有被标记为非素数，则将6、9、12等标记为非素数，一直到N为止，再数一遍素数数组中有多少素数。

代码

public class Solution {
    public int countPrimes(int n) {
        boolean[] prime = new boolean[n];
        Arrays.fill(prime, true);
        for(int i = 2; i < n; i++){
            if(prime[i]){
                // 将i的2倍、3倍、4倍...都标记为非素数
                for(int j = i * 2; j < n; j =  j + i){
                    prime[j] = false;
                }
            }
        }
        int count = 0;
        for(int i = 2; i < n; i++){
            if(prime[i]) count++;
        }
        return count;
    }
}

专线服务 idc机房托管 Primes LeetCode LeetCode_String leetcode_35_SearchIn

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

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

204. Count Primes

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

王笑朝 2019-07-30 16:58 评论0 收藏0
线性素数筛选（linear sieve for prime number）

摘要：转载到其他平台前也请通知我。算法分析由于我们每次寻找的素数时，都从开始，逐渐上除，最后到为止，确认是否是素数。接着继续排除其有关合数。在速度上有略微提升，但是它的算法是主动忽略的相关合数，实际意义并不是很大。偶然发现了这个和stackoverflow很像的地方。打算写些专栏，一方面，记录自己学到的东西。另一方面，也把这些分享给大家。无论是内容错误还是解释方式不好，都欢迎各位拍砖。转载...

biaoxiaoduan 2019-07-24 18:07 评论0 收藏0
[LeetCode] 204. Count Primes

Problem Count the number of prime numbers less than a non-negative number, n. Example: Input: 10Output: 4Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7. Solution class Solut...

cheukyin 2019-08-16 13:38 评论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
[LintCode/LeetCode] Super Ugly Number

摘要：建两个新数组，一个存数，一个存。数组中所有元素初值都是。实现的过程是，一个循环里包含两个子循环。两个子循环的作用分别是，遍历数组与相乘找到最小乘积存入再遍历一次数组与的乘积，结果与相同的，就将加，即跳过这个结果相同结果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...

wuyumin 2019-08-14 15:20 评论0 收藏0