Concise JAVA solution with explanation


  • 0

    Special thanks for StefanPochmann's precious advices!

    The basic idea is:

    Once we find a prime number i, then mark the composite numbers: 
    
    i*i, i*i+i, i*i+i*2 .. i*i+i*k < n
    

    Hints:

    1) 1 is not a prime number
    2) n is excluded
    3) As (i-1)*i is already marked in the previous case of i-1, so we can start from i*i
    

    Time complexity = O(n) + O(overlapped possibilities) - Detailed Analysis

    There're overlapped possibilities: 24=2x12, 3x8, 4x6..so it should be more than O(n). The time complexity is: O(n) + O(overlapped possibilities)

    public int countPrimes(int n) {
        boolean isComposite[] = new boolean[n];// isComposite[i]: If i is a composite number
        int count = 0;
        for (int i = 2; i < n; i++) {  
            if (!isComposite[i]) { 
                count++; 
                if (i < Math.sqrt(n))
                    for (int j = i * i; j < n; j += i)  
                        isComposite[j] = true;// Mark j as a composite number
            }
        }
        return count;
    }  
    

  • 0

    That's not O(n).


  • 0

    StefanPochmann, thanks for the comment, not very sure about the time complexity. Is it O(n)(outer loop)+O(n)(inner loop) = O(2n) = O(n)?


  • 0

    Oh, got it, there're overlapped possibilities: 24=2x12, 3x8, 4x6..so it should be more than O(n). The time complexity is: O(n) + O(overlapped possibilities )


  • 0

    The loops are nested, you can't just add their complexities.

    Let's do an experiment: Count how often isComposite[j] = true; gets executed. How often does it get executed for n being 10, 100, 1000, 10000, and 100000?


  • 0

    Yep, so it should be O(n) + O(overlapped possibilities ), if write like this, it will be executed n times at most. But we still have to use O(n) + O(overlapped possibilities ) to check if (!isComposite[j] ):

    for (int j = i; j < n; j += i)  
            if (!isComposite[j] )// <--
                isComposite[j] = true;// Mark j as a composite number

  • 0

    Haha, yeah, that check doesn't really help :-)

    There's some analysis here, though that's for an improved version (starting j at i is wasteful).


  • 0

    Awesome! It helps a lot, appreciate it, bro.


  • 0

    I see you start j at i*2 now. That's better, but you can start it even later...


  • 0

    We can start from i*i, LOL, thanks for your smart comment!


Log in to reply
 

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