Prime Interview

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:

• Python
• Javascript

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:

• Python
• Javascript

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:

• Python
• Javascript

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.

• Python
• Javascript

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(n²).

Hmm... So we have a solution that runs in O(n²) 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(n²). 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:

• Python
• Javascript

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(n^1.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(n²) to O(n^1.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!