Primality is a math-y topic. Sure, let’s implement the naive definition of what a prime number is. Excuse to talk about a bit of trivia I know.

Meta-note: not sure what the question-author is getting at with the Wikipedia mention. I don’t know if they’re “trying to make knowledge accessible”, or they don’t realize the limits of Wikipedia. I think that, and their encouragement that “there are no fancy optimizations required, but…” shows that they may have certain assumptions about their audience. Ah well!

Key facts:

1. n % m == 0 when m divides n. So we can recast the definition of primality as: for our input n, is there such an m such that n%m==0? I would venture that this is the “trivial” solution the author was thinking of.
2. A subtle complication is that n can be very big. Counting up to n may actually take a long time, even though the data itself is very small. If n were 100 digits, for instance, we’d just never finish. Fortunately, we’re not in that scenario.
3. Cute trick: say that n is not prime. So there must be some a*b=n. Try to convince yourself that one of a or b must be less than the square root of n, or a and b are the square root of n. Turning that around: if there’s some number that divides n, it will be found between 2 and sqrt(n). This is a much shorter loop (still a big loop!) to get through. It gets us across the finish-line, here.

import math
def is_prime(num):
    if num < 2: return False
    for i in range(2, int(math.sqrt(num))+1):
        if num % i == 0: return False
    return True

Closing Notes

I’m not a big fan of using numerical questions for interview questions. Obviously if it comes up in the work etc. etc., but these sort of questions seem more “targeted” (you either know the right approach or you don’t). This one is an interesting way to present the unintuitive fact that even though your input is “only” one number, your loop can run for a really long time! n, for O(n), is the number of values between 0 and num, which is exponential in the length of n. For the times I do other numerical questions, I’d list them here.