count primes
java
2 months ago
902 B
2
Indexable
Never
public class Solution { public int countPrimes(int n) { if (n < 3) { return 0; } if (n == 3) { return 1; } int count = 0; boolean[] primes = new boolean[n+1]; int i = 2; while (i*i < n) { isPrime(i, primes); i++; } i = 2; while (i < n) { if (!primes[i]) { count++; } i++; } return count; } private boolean isPrime(int k, boolean[] primes) { if (!primes[k]) { int i = k*2; while (i >= 0 && i < primes.length) { primes[i] = true; i += k; } } return !primes[k]; } }