Count Primes
Lesson 3 of 3 in Coddy's Interview Coding Challenges - Pack V course.
Challenge
HardWrite a function countPrimes that gets an integer n, and returns the number of prime numbers that are less than n.
Note: Time complexity must be better than O(nlogn)
1 <= n <= 1000000
Examples:
Input - 10
Expected Output - 4
Explanation - There are 4 prime numbers less than 10: 2, 3, 5, 7
Input - 13
Expected Output - 5
Explanation - There are 5 prime numbers less than 13: 2, 3, 5, 7, 11 - note that 13 does not count!
Try it yourself
int countPrimes(int n) {
// Write code here
}