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)?
Solution
Let's break this problem down. One way we could do this is to loop through all the numbers less than n and check if they're prime. We'll increment a count and that'll be it. (We'll go with this approach for now and discuss alternatives at the end.)
So first we'll need a function that tells us if a given number is prime or not, let's call it isPrime(k). This function should return true or false if a given number k is a prime number or not. You might think what we should do is loop through the numbers less than k and make a list of all the divisors, then check if the divisors list has length 2 (i.e. it is just 1 and k). Something like this:
def is_prime_divisors(k):
divisors = []
for i in range(1, k+1):
if k % i == 0:
divisors.append(i)
if len(divisors) == 2: # divisors == [1, k]:
return True
return False
function isPrimeDivisors(k) {
let divisors = [];
for (let i = 1; i <= k; i++) {
if (k % i == 0) {
divisors.push(i);
}
}
if (divisors.length == 2) { // just 1 and k
return true;
} else {
return false;
}
}
We check for a number being a divisor by using the modulo operator % which gives us the remainder after division, and see if the remainder is 0. If the remainder is 0, we know i divides k. If this happens, we add it to our divisors list and then at the end check if our list only has 2 numbers (1 and k).
This works but we can be go faster. Notice every number is divisible by 1 and itself. So really being prime means that it isn't divisible by any other numbers. So if we just check numbers between 1 and k, and if any of them is a divisor, then we can return early knowing k is not a prime. Now our function looks like this:
def is_prime_no_list(k):
for i in range(2, k):
if k % i == 0:
return False
# if we made it here, it's prime
return True
function isPrimeNoList(k) {
for (let i=2; i<k; i++) {
if (k % i == 0) {
return false;
}
}
// no divisors? then it's prime
return true;
}
This will be a lot faster on large numbers that have small divisors. For example if k = 1000000, before our function would loop 1 million times collecting all the divisors, now our function starts with 2, sees it's a divisor, and is done! It's way faster!
While we're at it, we can speed it up a bit more. If a number is even, then we know 2 is a divisor and we're done. However, if the number is odd then that means 2 doesn't divide it and nor do any even numbers divide it. So we can impove our loop to only loop over odd numbers after checking if 2 divides it, something like this:
def is_prime_odds(k):
# 2 is the only even prime
if k == 2:
return True
if k % 2 == 0:
return False
for i in range(3, k, 2):
if k % i == 0:
return False
return True
function isPrimeOdds(k) {
// first check if 2 b/c is even but prime
if (k == 2) {
return true;
}
// then we can check if even which means not prime
if (k % 2 == 0) {
return false;
}
for (let i=3; i<k; i+=2) {
if (k % i == 0) {
return false;
}
}
return true;
}
Ok so now we can check for primes, let's count em. This should be pretty straightforward, we just loop through the numbers less than n, check if they are prime, if so increment count, at the end return count. We'll also use the fact about even numbers so we only have to check odds after we count 2.
def prime_pi_odds(n):
if n < 2:
return 0
# start w/ counting 2
count = 1
# then only check odds
for k in range(3, n, 2):
if isPrime(k):
count += 1
return count
function PrimePiOdds(n) {
if (n < 2) {
return 0;
}
// start w/ counting 2
let count = 1;
// then only check odds
for (let k=3; k<n; k+=2) {
if (isPrime(k)) {
count++;
}
}
return count;
}
Ok looks good, our function works. Now let's move on to the second part and think about the time and space complexity. Our space complexity is easy, now that we aren't making a list of divisors, we're only keeping track of a few variables. This means the space we're using is constant so for space complexity we have O(1).
Now for time complexity, in PrimePi(n) we are looping up to n and in each loop isPrime(n) might loop up to n if the number is a prime, so we're doing n work n times so we have O(n2).
Hmm... So we have a solution that runs in O(n2) but the problem states we should make it faster than this, how? What about the even / odd trick, what did that do? By only checking odd numbers, this made our function roughly twice as fast, however this is a constant factor and doesn't change the fact that we're O(n2). This is probably the trickiest part of the problem, and may, but probably not, be asked in a real interview. Let's see how to answer it.
If a number k is composite, that means we write k = a*b for some a and b that are divisors of k. Now let's think about how big could a and b be? Since we're splitting our number in two with multiplication, this should make us think of square root. Could a and b both be bigger than the square root of k (sqrt(k))?
a > sqrt(k)
b > sqrt(k)
a*b > sqrt(k) * sqrt(k)
a*b > k
So no, if we're saying a*b = k, but if they're both bigger than the square root of k, then a*b would be bigger than k, not equal to it. For example let's look at 100. The sqrt(100) = 10 and if we factor 100 we might get 2*50 or 4*25 or 10*10. In all of these cases we see at least one of the numbers is less than or equal to the square root. This means if we're checking for primes, we need only check up to the square root of the number, because if it is factorable (and hence not prime), then any way that we factor it, one of it's factors will be less than or equal to it's square root. We can modify our isPrime function as follows:
import math
def is_prime_sqrt(k):
if k == 2:
return True
if k % 2 == 0:
return False
# now check up to and including the sqrt
sqrt_k = round(math.sqrt(k)) + 1 # + 1 to include the sqrt
for i in range(3, sqrt_k, 2):
if k % i == 0:
return False
return True
function isPrimeSqrt(k) {
if (k == 2) {
return true;
}
if (k % 2 == 0) {
return false;
}
// now check up to and including the sqrt
let sqrtK = Math.round(Math.sqrt(k)) + 1; // + 1 to include the sqrt
for (let i=3; i<sqrtK; i+=2) {
if (k % i == 0) {
return false;
}
}
return true;
}
With this improvement we are checking n numbers and each check now takes O(sqrt(n)). This means our overall time complexity is O(n*sqrt(n)) or O(n1.5)! Awesome, we've solved the problem in a pretty fast way!
Timing and other approaches
In a future blog post we might look at just how fast are these approaches. Does going from O(n2) to O(n1.5) really make that big of a difference? What about the divisor list vs returning early, does that really make a difference? We're planning to answer these questions in a follow blog post, stay tuned!
