My detailed understandable solution JAVA


  • 0
    C
    public class Solution {
        public int countPrimes(int n) {
            if(n<3)
                return 0;
            int[] arr = new int[n];
            for(int i=0; i<n; i++){
                arr[i]=i;
            }
            
            arr[0]=-1;
            arr[1]=-1;
            for(int i=2; i<n; i++){
                if(arr[i]!=-1){
                    int j=2;
                    while(i*j<n){
                        arr[i*j]=-1;
                        j++;
                    }
                }
            }
            int count=0;
            for(int i:arr){
                if(i!=-1)
                    count++;
            }
            return count;
        }
    }

  • 1
    L

    Why not use an array of booleans instead of an array of ints? And you can also set "j" to sqrt(i) or start j = i * i as you can see below:

    // Execution time: 28ms
    public class Solution {
        public int countPrimes(int n) {
            if(n <= 1) return 0;
            
            int sqrt = (int)Math.sqrt(n);
            boolean[] primes = new boolean[n];
            
            for(int i = 0; i < n; i++) {
                primes[i] = true;
            }
    
            primes[0] = false;
            primes[1] = false;
    
            for(int i = 2; i <= sqrt; i++) {
                if(!primes[i]) continue;
                
                for(int j = i * i; j < n; j += i) {
                    primes[j] = false;
                }
            }
            
            int ans = 0;
            for(int i = 0; i < n; i++) {
                if(primes[i]) {
                    ans++;
                }
            }
            
            return ans;
        }
    }

Log in to reply
 

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