Count Primes
程序员文章站
2024-03-14 20:42:23
...
题目
Count the number of prime numbers less than a non-negative number, n.
答案
class Solution {
public int countPrimes(int n) {
if(n <= 1) return 0;
int ans = 0;
// 0, 1 .... n - 1
boolean[] primes = new boolean[n];
primes[1] = false;
for(int i = 2; i < primes.length; i++)
primes[i] = true;
for(int i = 2; i <= Math.sqrt(n - 1); i++) {
if(primes[i]) {
for(int j = 2; i * j <= (n - 1); j++) {
primes[i * j] = false;
}
}
}
for(int i = 1; i < primes.length; i++)
if(primes[i] == true) ans++;
return ans;
}
}
推荐阅读
-
Count Primes
-
Count Primes
-
LeetCode-038:Count and Say
-
PHP中检索字符串的方法分析【strstr与substr_count方法】
-
Bitmasking and Dynamic Programming 实例 :Count ways to assign unique cap to every person
-
【Leetcode】204. Count Primes 204. 计数质数
-
数据库学习之MySQL (十一)—— 统计函数 COUNT MIN MAX AVG SUM
-
PHP中检索字符串的方法分析【strstr与substr_count方法】
-
LintCode 382 [Triangle Count]
-
Triangle Count (Lintcode 382)