题目

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

Example:

  1. Input: 10
  2. Output: 4
  3. Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

题意

计算小于指定整数n 的素数的个数。

思路

参考两种素数筛：埃氏筛和欧拉筛

代码实现

Java

埃氏筛

  1. class Solution {
  2.     public int countPrimes(int n) {
  3.         boolean[] p = new boolean[n];
  4.         int count = 0;
  5.         for (int i = 2; i < n; i++) {
  6.             if (p[i] == false) {
  7.                 count++;
  8.                 for (int j = 2 * i; j < n; j += i) {
  9.                     p[j] = true;
  10.                 }
  11.             }
  12.         }
  14.         return count;
  15.     }
  16. }

欧拉筛

  1. class Solution {
  2.     public int countPrimes(int n) {
  3.         boolean[] p = new boolean[n];
  4.         int[] primes = new int[n];
  5.         int count = 0;
  7.         for (int i = 2; i < n; i++) {
  8.             if (p[i] == false) {
  9.                 primes[count++] = i;
  10.             }
  11.             for (int j = 0; j < count; j++) {
  12.                 if (i * primes[j] >= n) {
  13.                     break;
  14.                 }
  15.                 p[i * primes[j]] = true;
  16.                 if (i % primes[j] == 0) {
  17.                     break;
  18.                 }
  19.             }
  20.         }
  22.         return count;
  23.     }
  24. }

JavaScript

  1. /**
  2.  * @param {number} n
  3.  * @return {number}
  4.  */
  5. var countPrimes = function (n) {
  6.   const sieve = []
  7.   const primes = []
  9.   for (let i = 2; i < n; i++) {
  10.     if (!sieve[i]) {
  11.       primes.push(i)
  12.     }
  14.     for (let j = 0; j < primes.length; j++) {
  15.       if (i * primes[j] >= n) break
  16.       sieve[i * primes[j]] = true
  17.       if (i % primes[j] === 0) break
  18.     }
  19.   }
  21.   return primes.length
  22. }