count_primes.java

/* Implement countPrimes(n), which calculates the number of primes that are strictly smaller than n.

Example 1:
Input: n=0
Output: 0

Example 2:
Input: n=10
Output: 4

Example 3:
Input: n=155
Output: 36

Example 4:
Input: n=5000000
Ouput: 348513

Constraints:
0 <= n <= 5 * 10^6

Time complexity: O(n^2)
Space complexity: O(n)

*/

class Solution {

    int countPrimes(int n) {
        if (n<=2) {
            return 0;
        }
        
        int counter = 0;
        /* notPrimesArray: Array in which every cell represents whether 
        its index number is non-prime or not. Initially every number is 
        considered prime (default value: false), but the opposite might be 
        determined later. */
        boolean[] notPrimesArray = new boolean[n];
        
        for (int i=2; i<n; i++) {
            /* Any product of i>=2 multiplied by any integer j>=2 is not prime.
            So the corresponding value of i*j in the array is changed to true. 
            This will only affect cells with an index number higher than the 
            current i, as i*j>i for any j>=2.*/
            for (int j=2; i*j<n; j++) {
                notPrimesArray[i*j] = true;
            }

            /* If a number is non-prime, the counter is updated. */
            if (notPrimesArray[i]==false) {
                counter++;
            }
        }

        return counter;
    }

};