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

  • 0
    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]){
            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.