My simple Java solution


  • 107
    J
    public class Solution {
        public int countPrimes(int n) {
            boolean[] notPrime = new boolean[n];
            int count = 0;
            for (int i = 2; i < n; i++) {
                if (notPrime[i] == false) {
                    count++;
                    for (int j = 2; i*j < n; j++) {
                        notPrime[i*j] = true;
                    }
                }
            }
            
            return count;
        }
    }

  • 2
    N

    Do you mined explaining me the purpose of making 'notPrime' array true by multiplying 'i' and 'j'. I'm unable to understand the logic behind. Thanks


  • 5
    J

    it starts from 2, the first prime, then mark the multip of 2 as true in notPrime, so the loop of i will skip them. the next prime is 3, do the same thing. Then it is 4, which 2*2, so the not prime is true, and will skip to next.


  • 14

  • 0
    Z

    this video is great!Thanks!


  • 16

    This can optimize the solution a little bit, since actually checking up to Math.sqrt(n) is enough.

    public int countPrimes(int n) {
        if(n <=1 ) return 0;
        
        boolean[] notPrime = new boolean[n];        
        notPrime[0] = true; 
        notPrime[1] = true; 
    
        for(int i = 2; i < Math.sqrt(n); i++){
            if(!notPrime[i]){
                for(int j = 2; j*i < n; j++){
                    notPrime[i*j] = true; 
                }
            }
        }
        
        int count = 0; 
        for(int i = 2; i< notPrime.length; i++){
            if(!notPrime[i]) count++;
        }
        return count; 
    }

  • 0
    K

    Sieve of Eratosthenes Ladies and Gents. Awesome code man.


  • 0
    C

    Nice solution!
    But instead of i++ here 'i' could be updated to next prime by finding next 'false' value in notPrime[]. This would optimize the code a bit.


  • 0
    R

    what is the time complexity of this ?
    EDIT: Never mind, the hints have the details


  • 0

    @chidong Will this optimization improve the run time in big O notation?


  • 0

  • 0

    @dryear no, but will, in reality.


  • 1
    L

    It seems that this code will cause overflow. Add a condition check to skip the inner for loop when i > sqrt(n) to avoid it.

    ......
                count++;
                if (i > Math.sqrt(n)) continue;
                for (int j = 2; i*j < n; j++) {
                    notPrime[i*j] = true;
    ......

  • 0
    This post is deleted!

  • 0
    W

    It seems this part of code could be changed like this

         if(Math.sqrt(n) < i) continue;
         for (int j = i; i*j < n; j++) {
             notPrime[i*j] = true;
         }
    

    this could be called Sieve of Eratosthenes
    https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


  • 0

    Similar solution, using BitSet:

    int countPrimes(int n) {
      BitSet compounds = new BitSet(n);
      for (int i = 2, end = (int) Math.sqrt(n); i <= end; i = compounds.nextClearBit(i + 1))
        for (int j = i * i; j < n; j += i)
          compounds.set(j);
      return Math.max(0, n - (compounds.cardinality() + 2));
    }
    

  • 0
    J

    Great solution, just add one more line to decrease the unnecessary check.

    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count=0;
        for(int i=2;i<n;i++) {
            if(!notPrime[i]) {
                count++;
                if(i*i<n) //check up to Math.sqrt(n)
                    for(int j=2;i*j<n;j++)
                        notPrime[i*j] = true;
            }
        }
        return count;
    }

  • 1
    M

    seems faster solution

    public class Solution {
        public int countPrimes(int n) {
            boolean[] notPrime = new boolean[n];
            int count = 0;
            for (int i = 2; i < n; ++i) {
                if (!notPrime[i]) {
                    count++;
                    // add i < Math.sqrt(n) to avoid overflow
                    for (int j = i * i;  i < Math.sqrt(n) && j < n ; j += i) {
                        notPrime[j] = true;
                    }
                }
            }
            return count;
        }
    }
    

  • 0
    P

    What would be the time complexity? Can we find a tighter bound to O(sqrt(n))?


  • 0
    P

    @Chidong anyway you're iterating O(n) to get the count


Log in to reply
 

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