count primes

mail@pastecode.io avatarunknown
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];
    }
}