7 min read

Prime Interview

Sep 30, 2020 9:42:28 PM

In this post we'll go over a potential technical interview problem.

White Board Question

Prime numbers are numbers that are only divisible by 1 and themselves. For example 7 is a prime number because it's only divisors are 1 and 7. The number 8 is not a prime number because it's divisors are 1, 2, 4, and 8. Numbers that are not prime are called composite. The first five prime numbers are 2, 3, 5, 7, and 11. Let's define a prime counting function, PrimePi(n), that counts how many prime numbers are less than a given number. So PrimePi(10) = 4 because there are 4 prime numbers (2, 3, 5, and 7) less than 10.

Your job is to write this PrimePi(n) function. What is the time complexity of you solution? What is the space complexity? Ideally this function should be fast. If it isn't already, can you make your solution faster than O(n2)?

Written by Greg Funchess