My JAVA solution with O(n^2) iteration only over odd numbers. 247ms


  • 0
    Q
    public class Solution {
        public int countPrimes(int n) {
            if (n<3){
    			return 0;
    		}
            boolean[] notPrimes = new boolean[n];
            double sq = Math.sqrt(n);
            for (int i=3;i<sq;i=i+2){//do odd
                int jLimit = (n-1)/i;
                for (int j=i;j<=jLimit;j=j+2){
                    notPrimes[i*j] = true;
                }
            }
            int count = 0;
            for (int i=2;i<n;i++){
            	if (notPrimes[i]){
            		count++;
            	}
            }
            return n/2-count;  //divide n by 2 to subtract evens
        }
    }

Log in to reply
 

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