// This is the Sieve of Eratosthenes method: fastest method to find all the primes less than a number
    int countPrimes(int n) {
        if (n < 2) 
            return 0;
        vector<bool> primes(n, true);
        primes[0] = primes[1] = false;
        int result = n - 2;
        for (int i = 2; i*i < n; ++i) {
            if (primes[i] == true) {
            	int j = i;
                while (i*j < n) {
                	if (primes[i*j] == true) {
                    	primes[i*j] = false;
                        --result;
                    }
                    ++j;     
                }
            }
        }
        return result;
    }
    
	// This function returns a bool saying if n is a primer number or not
	// Important to notice that if any divisor is not found before sqrt(n), no divisors will be found 
	// Good practice: j*j < n faster than j < sqrt(n). Furthermore sqrt(n) would not return an integer.
	bool is_prime(int n) {
        for (int j = 2; j*j <= n; ++j) {                
            if (n%j == 0) {
                return false;
            }
        }
        return true;
    }

    int countPrimes(int n) {
        int result = 0;
        for (int i = 2; i < n; ++i) {
            if (is_prime(i))
                ++result;
        }
        return result;
    }