Number and Math

What is this?

Three problems that each have an obvious slow solution and a short correct one. Testing every number up to n for primality is quadratic-ish; crossing off multiples is nearly linear. Checking every triple for the largest product is cubic; sorting once makes it two comparisons. Testing whether a number's only prime factors are 2, 3 and 5 by factorising it fully is unnecessary; dividing those factors out and checking what is left is three loops.

The pattern is the same each time: stop asking about every candidate and start eliminating whole classes at once.

💡 Fun fact: the Sieve of Eratosthenes is around 2,200 years old and still the practical way to list primes below a few million. Two refinements make it fast: start crossing off at p × p — every smaller multiple of p already has a smaller prime factor and was struck out earlier — and stop the outer loop at √n, because any composite below n has a factor no larger than that. Those two details take it from O(n log n)-ish to O(n log log n).

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: eliminate classes rather than testing individuals — divide known factors out, cross off multiples in bulk, or sort so that only two candidate answers remain to compare.

1. Divide the factors out

def is_ugly(n):
    if n <= 0:
        return False
    for p in (2, 3, 5):
        while n % p == 0:
            n //= p
    return n == 1

If dividing away every 2, 3 and 5 leaves exactly 1, the number had no other prime factors. The n <= 0 guard matters: zero would loop forever and negatives are excluded by definition.

2. Sieve, do not test

def count_primes(n):
    if n < 3:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p < n:
        if is_prime[p]:
            for multiple in range(p * p, n, p):     # start at p*p, not 2p
                is_prime[multiple] = False
        p += 1
    return sum(is_prime)

Starting at p × p is not a micro-optimisation — every multiple k × p with k < p has a prime factor smaller than p and was already crossed off when that smaller prime was processed.

3. Enumerate the sign cases

The largest product of three numbers is one of exactly two candidates:

• the three largest values, or
• the two most negative values times the largest.

The second wins when two large negatives multiply into a large positive. Sorting makes both readable in one line:

nums.sort()
return max(nums[-1] * nums[-2] * nums[-3],
           nums[0] * nums[1] * nums[-1])

There is a linear alternative that tracks the three largest and two smallest in one pass — worth mentioning as the O(n) improvement once the sorted version is on the board.

4. A 30-second worked example

nums = [-10, -10, 1, 3, 2]

sorted: [-10, -10, 1, 2, 3]

candidate A — three largest:      1 x 2 x 3       = 6
candidate B — two smallest x max: -10 x -10 x 3   = 300  ✅

answer = 300

Taking only the three largest gives 6 and is wrong. The two negatives cancel, which is exactly the case the second candidate exists to catch.

5. Where you'll actually meet this

• Cryptography and hashing. Prime generation underpins key selection and table sizing.
• Numeric libraries. Smooth-number tests (only small prime factors) decide whether a fast Fourier transform size is efficient.
• Financial and scoring calculations. Extreme-product selections where negative values are meaningful.
• Load and shard sizing. Choosing sizes with convenient factorisations.
• Competitive and simulation code. Precomputed prime tables are a standard warm-up step.

6. Problems in this chapter

▶ Ugly Number

Decide whether a number's only prime factors are 2, 3 and 5. Divide each out repeatedly and check that 1 remains.
Pattern: factor elimination. Target: O(log n) time, O(1) space.

▶ Count Primes

Count primes below n. Sieve of Eratosthenes, crossing off from p × p with the outer loop bounded by √n.
Pattern: sieve. Target: O(n log log n) time, O(n) space.

▶ Maximum Product of Three Numbers

Largest product of any three values. Sort, then take the better of the top three and the two smallest times the largest.
Pattern: sign-case enumeration. Target: O(n log n) sorted, or O(n) with a single tracking pass.

7. Common pitfalls 🚫

• Looping forever on zero in the factor test. Guard n <= 0 first.
• Starting the sieve at 2p. Correct but slower; p × p is the right lower bound.
• Running the outer sieve loop to n. It only needs to reach √n.
• Off-by-one on "below n". Count Primes excludes n itself, so the array has n entries indexed 0..n-1.
• Taking only the three largest for the product. Two negatives can beat them.
• Assuming at least one positive value exists. An all-negative array still has a well-defined answer.
• Overflow. Three values near 10³ are fine, but in fixed-width languages the general case needs a 64-bit type.

8. Key takeaways

1. Eliminate classes, not individuals. Cross off multiples; divide out factors.
2. p × p and √n are the two details that make a sieve fast.
3. Two candidates decide the extreme product, and the negative case is the one that gets missed.
4. Sort for clarity, then offer the linear version — showing both is stronger than either alone.
5. Guard the degenerate inputs. Zero, negatives and tiny n are where these fail.
6. Know the standard complexities. O(n log log n) for a sieve is worth saying precisely.
7. Why interviewers like it: short problems with well-known optimal solutions, so they reveal quickly whether you know the standard tools or are improvising.

Order: Ugly Number → Count Primes → Maximum Product of Three Numbers.