1. Description

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

2. Runtime Distribution

3. Submission Details

4. Example

Input 5
Output 2

5. Code

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active"]

public int countPrimes(int n) {
	if (n < 3) {
		return 0;
	}

	boolean[] primes = new boolean[n];
	int sqrt = (int) Math.ceil(Math.sqrt(n - 1));
	for (int i = 2; i <= sqrt; i++) {
		if (primes[i]) {
			continue;
		}
		for (int j = i + i; j < n; j += i) {
			primes[j] = true;
		}
	}

	int count = 0;
	for (int i = 2; i < n; i++) {
		if (!primes[i]) {
			count++;
		}
	}
	return count;
}

[/restab]
[/restabs]

6.Test

[restabs alignment="osc-tabs-right" responsive="true" icon="true" text="More" seltabcolor="#fdfdfd" seltabheadcolor="#000" tabheadcolor="blue"]
[restab title="Java" active="active" ]

public class LeetCode0204 {
	public int countPrimes(int n) {
		if (n < 3) {
			return 0;
		}

		boolean[] primes = new boolean[n];
		int sqrt = (int) Math.ceil(Math.sqrt(n - 1));
		for (int i = 2; i <= sqrt; i++) {
			if (primes[i]) {
				continue;
			}
			for (int j = i + i; j < n; j += i) {
				primes[j] = true;
			}
		}

		int count = 0;
		for (int i = 2; i < n; i++) {
			if (!primes[i]) {
				count++;
			}
		}
		return count;
	}

	public static void main(String[] args) {
		LeetCode0204 leetcode = new LeetCode0204();
		System.out.println(leetcode.countPrimes(5));
	}
}

[/restab]
[/restabs]