Simple Solution


  • 0
        public static int countPrimes(int n) {
    		if(n<3) return 0;
    		boolean[] primes = new boolean[n];
    		int count = n-2; // 0 and 1 are not prime, 2 is the first prime
    		for(int i=2;i<n;i++) {
    			if(!primes[i])
    				for(int j=i+i;j<n;j+=i) if(!primes[j]) { primes[j]=true; count--; }
    		}
    		return count;
    	}
    

    This solution uses the Sieve of Eratosthenes:

    1. if n<3 then the number of primes is 0 (0 and 1 are not primes)
    2. create an array of boolean of length n
    3. initialize the count of primes to n-2 (initially we consider all
      primes except for 0 and 1 that we already said are not primes)
    4. starting from int i=2 take this number as the smallest prime
    5. mark all multiples of i smaller than n as not prime. Every time an element is
      marked as true (that indicates is not a prime), decrement the prime
      count (count--).
    6. take the next i in the sequence that is not marked and repeat the
      process from point 5.
    7. at the end we will have in the count variable the number of primes (the
      number of elements that are not marked in the inner loop).

  • 0
    L

    if n eqaul INT_MAX, you need 2*32 bits, about 4GB.


Log in to reply
 

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