Use BitSet which is supposed to be better than a boolean array


  • -1
    J

    import java.util.BitSet;

    /**

    • Created by bear on 8/23/15.
      */
      public class Solution {

    public int countPrimes(int n) {
    if (n <= 2){
    return 0;
    }
    // index i is set if i is not prime
    // i [0 ... n)
    BitSet isPrime = new BitSet(n);
    isPrime.set(0);
    isPrime.set(1);
    int i = 2;
    while(ii < n){
    for(int j=i
    i; j<n; j+=i){

                isPrime.set(j);
                
            }
            i = isPrime.nextClearBit(i+1);
        }
    
        return n - isPrime.cardinality();
    }
    

    }


Log in to reply
 

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