Math for DSA: Digits, Divisors, GCD and Primes

Complexity and Math · 35 min

DSA foundations · Number theory

Number tricks that turn n steps into √n

Digits, divisors, GCD and primes all look like they need a loop up to n. Each one has a shortcut you can derive rather than memorise — and the sieve finds every prime below 30 in 24 pencil strokes.

Strike out the composites up to 30, one prime at a time →
Digitspeel with % 10, drop with / 10 — about log₁₀ n turns
→
Divisorsthey come in pairs meeting at √n, so stop there
→
GCDreplace (a, b) with (b, a mod b) until b is 0
→
Primesstrike every multiple once, never test twice

01 The idea

Stop looping to n

A number problem hands you one integer and asks something about it. How many digits does it have. What are its divisors. Is it prime. What does it share with a second number. The first loop that comes to mind runs from 1 to n and checks every value on the way. For n = 30 that costs nothing. For n = 10⁹ it is a program that never finishes.

Every technique in this module is the same correction applied four different ways. Digits fall off ten at a time, so a 9-digit number takes 9 turns and not a billion. Divisors come in pairs that meet at √n, so you only ever search one half of each pair. A remainder is always smaller than the number you divided by, so Euclid's GCD collapses in a handful of steps. And when you want every prime below N, you stop asking each number a question and start striking out multiples instead.

If a number problem makes you loop from 1 to n, you are almost always doing too much work. Divisors pair up around √n, remainders shrink fast, and exponents can be halved.
DivisorA number d divides n when n % d == 0, meaning the division leaves no remainder. 30 has eight divisors: 1, 2, 3, 5, 6, 10, 15, 30.
PrimeA whole number above 1 whose only divisors are 1 and itself. 2, 3, 5, 7 and 11 are prime. 1 is not, because it has only one divisor.
CompositeA whole number above 1 that is not prime, so it has a divisor strictly between 1 and itself. Every composite up to 30 is a multiple of 2, 3 or 5.

02 Worked example

The Sieve of Eratosthenes up to 30

Write the numbers 2 to 30 on paper. Circle the smallest one you have not touched — that is 2, and it must be prime, because nothing smaller crossed it out. Now cross out every multiple of 2 above it. Move to the next uncrossed number and repeat. Each row below is one prime's turn, showing only the numbers it strikes for the first time.

p = 2468101214161820222426283014 struck — every even number after 2
p = 39152127starts at 3² = 9; of its 8 multiples, 12 18 24 30 were already gone
p = 444 is already crossed — skip it, its multiples are multiples of 2
p = 525starts at 5² = 25; the only other multiple, 30, was already gone
p = 6366 × 6 = 36 is past 30 — stop, nothing is left to strike
survivors235711131719232910 primes up to 30

Count what the sieve actually did. It wrote 24 crosses in total — 14 for 2, 8 for 3, 2 for 5 — and 19 of them landed on a number for the first time, which is exactly the number of composites between 2 and 30. It never once asked "is 17 prime?". It found out because nobody crossed 17 out. That is the whole trade: you give up asking about one number and you get every answer in the range at once.

03 Mechanics

Why √n is enough

Before the sieve comes the single-number question: is 29 prime? The obvious loop divides 29 by every number below it. The fix is one line of the loop condition, and it is worth deriving once instead of memorising. Suppose n = a × b and both a and b were greater than √n. Then their product would be greater than n, which contradicts the assumption. So every composite has a divisor at or below √n. Search there, find nothing, and there is nothing to find anywhere.

Naive — divide by everything

isPrime(n):    if n < 2: return false    for d = 2 to n - 1:        if n % d == 0: return false    return true

Bounded — stop at the square root

isPrime(n):    if n < 2: return false    d = 2    while d * d <= n:        if n % d == 0: return false        d = d + 1    return true

For n = 29 that is 4 divisions instead of 27. The naive loop tries every d from 2 to 28. The bounded loop stops after d = 5, because 6 × 6 = 36 is already past 29. The gap widens with n: at n = 10⁹ it is 31,623 divisions against a billion.

The test is d * d <= n, not d <= sqrt(n). Integer multiplication is exact. sqrt returns a floating-point value, and for large n the rounding can land one below the true root, skip the last divisor and report a composite as prime. Same loop, no floating point, no edge case.

Looping to n/2 is not the same fix. It skips the top half and still costs 13 divisions for 29 instead of 27 — half the work, same growth rate. √n is a different curve, not a smaller constant, and that is the distinction an interviewer is listening for.

The same bound lists every divisor. Walk d from 1 while d * d <= n; each hit hands you two divisors, d and n / d. For 30 the five tests d = 1, 2, 3, 4, 5 produce the pairs (1, 30), (2, 15), (3, 10) and (5, 6) — all 8 divisors from 5 divisions. Add d only once when d * d == n, or a perfect square counts its middle divisor twice.

Euclid's rule is the same shrink wearing different clothes: gcd(a, b) = gcd(b, a mod b), because anything dividing both a and b also divides a − qb. Starting from gcd(30, 18) the pair becomes (18, 12), then (12, 6), then (6, 0) — the answer is the last non-zero value, 6.
The LCM trap. Write lcm(a, b) = a / g * b and never a * b / g. Divide first, because a * b can overflow long before the answer does. Here lcm(30, 18) = 30 / 6 × 18 = 90.

05 Cheat sheet

Eight routines and what they cost

TaskMethodCost
Count or reverse the digits of npeel with n % 10, drop with n / 10O(log n)
Is n prime?trial-divide d while d*d <= nO(√n)
List every divisor of nfor each d ≤ √n that divides n, take d and n/dO(√n)
Prime factorise ndivide out each d from 2 while d*d <= n, keep the leftoverO(√n)
Every prime up to NSieve of EratosthenesO(N log log N)
Test each of 2..N on its ownthe √n check, N timesO(N√N)
gcd(a, b)while b: a, b = b, a mod bO(log min(a,b))
lcm(a, b) and ab mod ma / g * b; square the base and halve bO(log n)
√n, not n/2Stopping at n/2 skips half the loop and is still linear. At n = 10⁹ that is 500 million divisions against 31,623. Halving a constant is not the same as changing the growth rate.
1 is not prime, 2 isA prime needs exactly two distinct divisors, and 1 has one. 2 is prime and is the only even prime, which is why tuned versions handle it separately then step d by 2. Every implementation opens with if n < 2: return false.
Memory is the sieve's real limitOne byte per number to 10⁷ is 10 MB and fine. To 10⁹ it is a gigabyte and is not. Past that you switch to a segmented sieve over a window, or to Miller–Rabin for a single number.

06 Where & why

The sieve is not a primality test

The sieve answers "which numbers in this whole range are prime" in one pass, and it pays for that by needing the entire range in memory before you ask a single question. If you only ever ask about one number, it is the wrong tool and the √n check is the right one.

Reach for the sieve when…

You will ask many timesSieve once to N, then every query is an array lookup. Sieving to 10⁶ costs roughly 3 million operations and one √n test costs up to 1,000, so the sieve pays for itself past a few thousand queries.
N is known and fits in memoryOne byte per number to 10⁷ is 10 MB. If you cannot state the upper bound before the program starts, the sieve has nothing to allocate and the choice is made for you.
You want more than yes or noThe same pass can record the smallest prime factor of every number, which turns factorising any n into an O(log n) walk. A per-number test gives you one bit and nothing else.
The range is small and denseCounting the primes below 10⁶, listing them, or summing them all fall out of one pass over the finished array, with no per-number test anywhere. This is the shape of most contest and screening-round questions.

Use something else when…

SituationBetter choiceWhy
One number with 18 digitsMiller–RabinAn array of 10¹⁸ flags does not exist. Miller–Rabin answers in a few dozen modular exponentiations, and with a fixed set of bases it is deterministic for every 64-bit input.
Primes inside [10⁹, 10⁹ + 10⁶]Segmented sieveSieve only to √(10⁹) ≈ 31,623 for the base primes, then strike their multiples inside the window. Memory tracks the window size, not the endpoint.
Factorising one large semiprimePollard's rhoTrial division to √n is 10⁹ steps at n = 10¹⁸. Pollard's rho runs in roughly O(n1/4) and is what real factorisation code starts with.
You only need gcd or lcmEuclidNo primes are involved at all. Factorising both numbers to find common factors is far slower and can overflow; the remainder loop finishes in a handful of divisions.
In real code you will call math.gcd and a library primality test. What survives from this lesson is the reflex: when a loop runs to n, ask whether the answer actually lives below √n, or whether one pass over the whole range can answer every question at once.

07 Interview questions

What they actually ask

Number-theory questions turn up in screening rounds because they are short to state and easy to mark. What is being tested is whether you can justify the bound, not whether you remember the loop.

Walk me through the Sieve of Eratosthenes.
You write down every number from 2 to N and assume they are all prime. Take the smallest one you have not crossed out — that is 2 — and cross out every multiple of it. Move to the next number still uncrossed and repeat. Whatever survives is prime, so for N = 30 you are left with 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
Why does the outer loop stop at √N?
Because every composite up to N has a prime factor at or below √N. If both factors of a number were larger than √N, their product would be larger than N. So once p passes √N there is nothing left to strike — every composite has already been crossed out by a smaller prime. For N = 30 you stop after p = 5, because 6 × 6 = 36 is past 30.
Why does the inner loop start at p² and not at 2p?
Every multiple of p below p² has a factor smaller than p, so a smaller prime already crossed it out. When p = 5, the multiples 10, 15 and 20 were struck by 2 and 3 long before. It does not change the big-O, but it removes redundant writes: sieving to 30 from p² writes 24 crosses, and starting each prime at 2p writes 28.
What is the time and space complexity of the sieve?
O(N log log N) time and O(N) space. The inner loop runs about N/p times for each prime p, and the sum of 1/p over the primes up to N grows like ln ln N. The line that skips an already-crossed p is what keeps it there — sieve with every number instead of only the primes and that sum becomes the harmonic series, which is ln N.
Why is it enough to trial-divide a single number up to √n?
If n = a × b and both a and b were greater than √n, then a × b would be greater than n, which is impossible. So at least one factor sits at or below √n. Test every d from 2 up to there, find nothing, and n is prime — for n = 29 that is 4 divisions instead of 27.
Is 1 prime? What about 2, 0 and negative numbers?
1 is not prime, because a prime needs exactly two distinct divisors and 1 has only one. 2 is prime, and it is the only even prime, which is why tuned code handles it separately and then steps d by 2. Neither 0 nor any negative number is prime, so every implementation opens with if n < 2: return false — forgetting that line is the most common failed test case in this question.
Explain Euclid’s algorithm and prove that it terminates.
gcd(a, b) = gcd(b, a mod b). Anything that divides both a and b also divides a − qb, so the new pair has exactly the same set of common divisors as the old one. It terminates because a mod b is strictly smaller than b, so the second value decreases every turn and must reach 0. gcd(30, 18) goes (30, 18) → (18, 12) → (12, 6) → (6, 0), so the answer is 6.
How many steps does Euclid take?
O(log min(a, b)) divisions. Lamé’s theorem bounds it at about five times the number of decimal digits in the smaller input, and the worst case is a pair of consecutive Fibonacci numbers. Two 64-bit values therefore finish in under 100 divisions — the worst pair that fits, two consecutive Fibonacci numbers, needs 91. The subtract-the-smaller version is the same idea but can take O(a) steps — gcd(1071, 462) is 3 divisions or 12 subtractions.
How do you get the LCM, and what goes wrong?
lcm(a, b) = a / gcd(a, b) * b. Divide before you multiply: a * b overflows long before the true answer does, and the gcd always divides a exactly, so the division is safe. For our pair that is 30 / 6 × 18 = 90. The identity gcd × lcm = a × b holds for positive integers, and lcm(0, x) is defined as 0.
Sieve or per-number test — how do you choose?
One query, use the √n test; many queries over a known range, sieve. Sieving to 10⁶ costs roughly 3 million operations once and then answers in O(1), while a single √n test costs up to 1,000 divisions, so the sieve pays off past a few thousand queries. Memory decides the rest — a sieve to 10⁹ needs a gigabyte-scale array, so above that you use Miller–Rabin.
How would you compute a to the power b, mod m, without looping b times?
Exponentiation by squaring. Halve the exponent each turn: square the base every step, and whenever the current bit of b is 1, multiply the base into the running result, taking the mod after every multiplication so nothing overflows. That is at most 2 log₂ b multiplications — for b = 1000 it is 10 squarings plus 6 multiplies into the result, 16 operations instead of 999.
Where does any of this show up in real code?
Rarely in this form — you call math.gcd and a library primality test. It shows up as the pattern instead: reducing a fraction is one gcd call, hashing and public-key cryptography lean on modular exponentiation, and any problem phrased as "all X up to N" is a sieve in disguise, including smallest-prime-factor tables, divisor counts and Euler’s totient. Interviews test the √n and log n reasoning, not the typing.

08 Practice problems

Six to work through

For each one, state the bound of your loop and why it is enough before you write anything. Every problem here is solvable with the four moves in this lesson and nothing else.

Palindrome number

Easy
Return true when the integer n reads the same forwards and backwards, without converting it to a string.
Follow-up
You have to rebuild the number from its digits. Negatives and trailing zeros both break the naive comparison — 10 reversed is 1, and every negative number reversed puts the minus sign in the wrong place.
Show the hint
Peel a digit with n % 10 and rebuild with r = r * 10 + digit, then compare r with the original; reject negatives before the loop starts.

Most balanced factor pair

Easy
Print the two factors whose product is n and whose difference is smallest — 48 gives 6 × 8, 36 gives 6 × 6, 37 gives 1 × 37.
Follow-up
A prime n has no divisor at all strictly between 1 and √n, so the loop can finish having found nothing. Code that prints whatever pair it happened to be holding fails on exactly the primes.
Show the hint
Keep a best pair and start it at (1, n); then walk d while d * d <= n and overwrite the best pair with (d, n / d) on every hit.

Prime factorisation

Medium
Return the prime factors of n with multiplicity, so 360 gives 2 2 2 3 3 5.
Follow-up
You never need a primality test inside the loop. Dividing each factor out as you find it means the next divisor you hit must be prime — and whatever is left above 1 after d passes √n is itself prime.
Show the hint
While n % d == 0, record d and divide n by d before you increase d; then check the leftover once the loop ends.

GCD of a whole array

Medium
Given n positive integers, return the greatest common divisor of all of them.
Follow-up
GCD is associative, so it folds left to right over the array. Once the running value reaches 1 no later element can change it, so a good solution can stop reading input early.
Show the hint
Start with the first element and fold g = gcd(g, next) across the rest; break the moment g becomes 1.

Primes in a range, many queries

Medium
Answer q queries, each asking how many primes lie in the range [L, R] with R up to 10⁶, in O(1) time per query after preprocessing.
Follow-up
Testing each number per query is O(q × R√R) and will time out. A sieve alone is not enough either — a boolean array still needs a loop per query.
Show the hint
Sieve once, then build a prefix-sum array where cnt[i] is the number of primes up to i; the answer to a query is cnt[R] − cnt[L − 1].

Smallest prime factor sieve

Hard
Preprocess once so that any n up to 10⁶ can be prime-factorised in O(log n), then answer q factorisation queries.
Follow-up
Store the prime that struck each number instead of a boolean. The catch is which prime gets recorded — the sieve must not let a larger prime overwrite a smaller one that already claimed that slot, so the write has to be conditional.
Show the hint
In the inner loop set spf[m] = p only when spf[m] is still empty; then factorise by repeatedly dividing n by spf[n].