`

Count Primes

阅读更多
Description:

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

给定一个整数,返回小于它的所有质数。我们借助一个布尔数组,来记录哪些数已经被标记为不为质数,每次循环的时候都从一个质数开始。最后只需要遍历一遍布尔数组中值为true的元素个数就可以了。代码如下:
public class Solution {
    public int countPrimes(int n) {
        boolean[] prime = new boolean[n];
        Arrays.fill(prime, true);
        int count = 0;
        for(int i = 2; i < n; i++) {
            if(prime[i]) {
                for(int j = i * 2; j < n; j += i) {
                    prime[j] = false;
                }
            }
        }
        for(int i = 2; i < prime.length; i++) {
            if(prime[i])
                count ++;
        }
        return count;
    }
}
1
1
分享到:
评论

相关推荐

    Leetcode 计数质数.sln

    LeetCode 204的题目是“计数质数”(Count Primes),要求统计所有小于非负整数n的质数的数量。解决这个问题的关键是高效地识别质数,并减少不必要的重复检查。在C#中,一个常见的解决方案是使用埃拉托斯特尼筛法...

    leetcode数组下标大于间距-LeetCode:努力的一天要i++

    countPrimes(int n) { int count = 0; for(int i = 2; i &lt; n; i++) { bool sign = true; for(int j = 2; j &lt; i; j++) { if(i % j == 0) { sign = false; break; } } if(sign) count++; ; } return count; } ...

    LeetCode最全代码

    ...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...

    JS实现计算小于非负数n的素数的数量算法示例

    本文实例讲述了JS实现计算小于非负数n的... var countPrimes = function(n) { let flagArray = [], result = 0; for(let i = 2; i &lt; n; i++){ if(flagArray[i] === undefined){ flagArray[i] = 1; result++;

    python求质数的3种方法

    本文为大家分享了多种方法求质数...def countPrimes1(self, n): :type n: int :rtype: int if n&lt;=2: return 0 else: res=[] for i in range(2,n): flag=0 # 质数标志,=0表示质数 for j in range(2,i):

    怎么把leetcode切成英文-Code-Problem-Practice:重新编码我的编码练习程序

    countPrimes(int n) { if (n isPrime(n+1, 1); int count = 1; for (int i=3; i&lt;n; i+=2){ if (isPrime[i]==1) { count++; for (int j = i; j&lt;=n/i; j+=2) isPrime[j*i] = 0; } } return count; } :star: 2020...

    leetcode数组下标大于间距-problems:问题

    leetcode数组下标大于间距 problems 1.Exercise ...CountPrimes:计算小于n的素数个数,数学 bestsubstring:将字符串尽可能分割为多个部分,各子串不包含相同字符暴力 2pow:计算2的N次幂 dp/ chrous:相

    go-prime-generator:Golang 上的素数生成器

    go-prime-发电机 Golang 上的质数生成器具有超时功能 安装 ... #如何 package main ... //primes count fmt . Println ( len ( primes )) } func generate ( maxN int , timeout time. Duration ) [] i

    iws-cicd-probe

    名称&gt; http://&lt;server&gt;:&lt;port&gt;/hello/&lt;name&gt; 素数100 http://&lt;server&gt;:&lt;port&gt;/primes/ 素数&lt;count&gt; http://&lt;server&gt;:&lt;port&gt;/primes/&lt;count&gt;构建并运行简单说明(Debian / Ubuntu) 安装要求: apt updateapt install...

    cicd-workflow

    名称&gt; http://&lt;server&gt;:&lt;port&gt;/hello/&lt;name&gt; 素数100 http://&lt;server&gt;:&lt;port&gt;/primes/ 素数&lt;count&gt; http://&lt;server&gt;:&lt;port&gt;/primes/&lt;count&gt;构建并运行简单说明(Debian / Ubuntu) 安装要求: apt updateapt install...

    cicd-workshop

    名称&gt; http://&lt;server&gt;:&lt;port&gt;/hello/&lt;name&gt; 素数100 http://&lt;server&gt;:&lt;port&gt;/primes/ 素数&lt;count&gt; http://&lt;server&gt;:&lt;port&gt;/primes/&lt;count&gt;构建并运行简单说明(Debian / Ubuntu) 安装要求: apt updateapt install...

Global site tag (gtag.js) - Google Analytics