Count Primes (E)
题目
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.
题意
计算小于指定整数n 的素数的个数。
思路
代码实现
Java
埃氏筛
class Solution {
public int countPrimes(int n) {
boolean[] p = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (p[i] == false) {
count++;
for (int j = 2 * i; j < n; j += i) {
p[j] = true;
}
}
}
return count;
}
}
欧拉筛
class Solution {
public int countPrimes(int n) {
boolean[] p = new boolean[n];
int[] primes = new int[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (p[i] == false) {
primes[count++] = i;
}
for (int j = 0; j < count; j++) {
if (i * primes[j] >= n) {
break;
}
p[i * primes[j]] = true;
if (i % primes[j] == 0) {
break;
}
}
}
return count;
}
}
JavaScript
/**
* @param {number} n
* @return {number}
*/
var countPrimes = function (n) {
const sieve = []
const primes = []
for (let i = 2; i < n; i++) {
if (!sieve[i]) {
primes.push(i)
}
for (let j = 0; j < primes.length; j++) {
if (i * primes[j] >= n) break
sieve[i * primes[j]] = true
if (i % primes[j] === 0) break
}
}
return primes.length
}