Accepted Java Solution


  • 5
    G
    public class Solution {
        public int countPrimes(int n) {
            int count=0;
            boolean[] nums = new boolean[n];
            for(int i=2; i<nums.length; i++){
                if(!nums[i]){
                    count++;
                    for(int j=2*i; j<nums.length; j=j+i){
                            nums[j] = true;
                    }
                }
            }
            return count;
        }
    }

  • 0
    S

    Some explanation to help us walk thru the logic behind your code would be greatly appreciated! :)


  • 0
    D

    Why the time complexity is O(nlogn). I think it is O(n^2) because the number of iterations for each inner loop is n/2, n/3, n/5, n/7, ... So it is still n * n


  • 0
    D

    I agree, it's not O(nlogn)


  • 0
    G
    This post is deleted!

  • 0
    G

    Thanks for the correction guys. I agree it's not n log n. I'm sorry I just didn't think it through.


Log in to reply
 

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