21ms easy java optimal solution


  • 2
    G
    public int countPrimes(int n) {
        if(n < 3) return 0;	
    	boolean[] primes = new boolean[n];
    	
    	// first mark off even numbers
    	for(int i = 4; i<n;i=i+2){
    		primes[i] = true;
    	}
    
        // mark off other non-primes, skip the even numbers
    	for(int i=3; i < Math.sqrt(n); i++) {
    		if(!primes[i]){
    			for(int j = i*i; j < n; j += 2*i) {
    				primes[j] = true;
    			}
    		}
    	}
    	int count = 0;
    	for(int i=2;i<n;i++){
    		if(!primes[i]) count++;
    	}
    	return count;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.