[LeetCode] Count Primes

Count Primes

Description:

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

Solution: Hash table + Sieve of Eratosthenes

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Solution { public int countPrimes(int n) { if (n < 2) return 0; int[] arr = new int[n]; Arrays.fill(arr, 0); for (int i = 2; i < n; i++) { if (arr[i] == 1) { continue; } for (int j = 2*i; j < n; j += i) { arr[j] = 1; } } int sum = 0; for (int i = 2; i < n; i++) { sum += (1 - arr[i]); } return sum; } }

A slightly optimized version: 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

public class Solution { public int countPrimes(int n) { if (n < 2) return 0; int[] arr = new int[n]; Arrays.fill(arr, 0); for (int i = 2; i <= Math.sqrt(n-1); i++) { if (arr[i] == 1) { continue; } for (int j = i*i; j < n; j += i) { arr[j] = 1; } } int sum = 0; for (int i = 2; i < n; i++) { sum += (1 - arr[i]); } return sum; } }