Java- simple n clean - use BitSet as the boolean array to count the prime


  • 0
    J
    public class Solution {
    public int countPrimes(int n) {
    	if (n <= 2)
    		return 0;
    	
    	BitSet isPrime = new BitSet(n);
    	for (int i = 2; i < n; i++) isPrime.set(i);;
    	
    	for (int i = 2; i*i < n; i++) {
    		if (!isPrime.get(i))
    			continue;
    		else {
    			for (int j = i*i; j < n; j += i) {
    				isPrime.set(j, false);;
    			}
    		}
    	}
    
    	return isPrime.cardinality();
    }
    

    }


Log in to reply
 

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