Java solution using the logic mentioned in the question


  • 2
    S
    public class Solution {
        public int countPrimes(int n) {
            if(n<=2) return 0;
            boolean[] flag = new boolean[n];
            // 2 is taken into consideration
            int result = 1; 
        
            //there is no point checking for even numbers anywhere in the loops
            // tried the same logic using HashSet but it was giving TLE. 
            for(int i = 3; i<n ; i = i+2){
                if(!flag[i-1]){
                    result++;
                    for(int k = 3; k*i < n; k = k+2){
                        if(!flag[k*i-1])
                            flag[k*i-1]= true;
                    }
                }
            }
            return result;
            
        }
    }

Log in to reply
 

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