Basic Math for DSA: Primes, Sieve, GCD & Modulo (Java)

Check if a number is prime. Easy, right? Loop from two to n, and test every number. For n equals one billion, that's a billion steps. Your code times out.

Now, the smart way. Stop at the square root. That's about thirty-one thousand steps. Same answer, thirty thousand times faster. And that's just one trick.

Welcome back to Compiled Canvas. This is Episode Five of our DSA series. In Episode Four, we set up our Java toolkit. Today, we cover the math you need for DSA. Not school math. Just the handful of ideas that keep showing up in coding interviews.

Here's the plan. Digits, and how to pull a number apart. Divisors, in O of root n. Prime numbers, and the fast way to check them. The Sieve of Eratosthenes, to find every prime up to n. Prime factorization. GCD and LCM, with Euclid's algorithm. Modulo arithmetic, and why every problem says ten to the nine plus seven. Fast power. A few formulas and Java math traps. A cheat sheet for which tool to use. And a quiz at the end.

Let's go.

First, digits. Two operators do all the work. n modulo ten gives you the last digit. And n divided by ten removes the last digit.

Take one two three four. Modulo ten gives four. Divide by ten, and you're left with one two three. Repeat until n becomes zero, and you've visited every digit, from right to left.

So how many steps is that? One step per digit. And a number n has about log base ten of n digits. So it's O of log n. Even a number with eighteen digits takes only eighteen steps.

With this one loop, you can count the digits, add them up, or reverse the number. To reverse, start with zero. At each step, multiply the result by ten, and add the last digit. One two three four becomes four three two one.

And to check if a number is a palindrome, reverse it, and compare it with the original. Just watch out: reversing a big int can overflow. So keep the reversed value in a long.

Next, divisors. A divisor of n is a number that divides it with no remainder. The slow way checks every number from one to n. That's O of n.

But here's the key idea. Divisors come in pairs. If i divides n, then n divided by i divides n too. Take thirty-six. One and thirty-six. Two and eighteen. Three and twelve. Four and nine. And six and six.

Look at the pairs. In every pair, one number is at most six, the square root of thirty-six. So you only need to check up to the square root. For every i that divides n, you get two divisors at once: i, and n divided by i.

One detail: when i times i equals n, like six times six, the pair is the same number. Count it only once.

That takes us from O of n to O of root n. For n equals one billion, that's thirty-one thousand steps, instead of a billion.

And in code, don't write i less than or equal to the square root of n. Write i times i, less than or equal to n. It avoids decimal numbers completely. And if n is close to the int limit, make i a long, so i times i can't overflow.

Now, prime numbers. A prime is a number greater than one, whose only divisors are one and itself. Two, three, five, seven, eleven. And remember: one is not a prime. And two is the only even prime.

To check one number, use the same trick. If n has a divisor, it has one at or below its square root. So loop i from two, while i times i is at most n. If any i divides n, it's not prime. If none does, it is. That's O of root n.

But what if you need every prime up to n? Checking each one costs n times root n. Too slow. That's where the Sieve of Eratosthenes comes in.

Make a boolean array, and mark every number from two to n as prime. Then start at two. Two is prime, so cross out all its multiples: four, six, eight, ten, and so on. Move to three. It's still marked, so it's prime. Cross out its multiples. Four is already crossed out, so skip it. Five is prime. Cross out its multiples. Keep going.

Here's the clever part. For each prime p, start crossing out at p times p, not at two times p. Every smaller multiple was already crossed out by a smaller prime. And that's why you can stop once p times p is bigger than n.

Whatever is still marked at the end is prime. The time is O of n log log n, which is almost linear. The only cost is memory: one boolean for each number, so it works up to about ten million.

So, one number? Check up to root n. Every prime up to n? Use the sieve.

Next, prime factorization: writing a number as a product of primes. Take three hundred sixty. That's two times two times two, times three times three, times five.

Here's how. Start with i equals two. While i divides n, record i, and divide n by i. When it stops dividing, move to the next i. And again, stop when i times i is bigger than n.

If whatever is left at the end is bigger than one, it's a prime factor too. That's the one big prime that's above the square root.

You never need to check if i is prime. By the time you reach i, all its smaller factors have already been divided out. So only primes can divide what's left.

And it's fast. The loop runs to the square root, so prime factorization is also in O of root n.

Quick pause, before we go further. If you're finding this video valuable, hit subscribe to Compiled Canvas, and turn on the bell. It's free, it takes one second, and it helps me keep making this complete DSA series for you. Alright, back to it.

Now, the GCD: the greatest common divisor. It's the largest number that divides both a and b. The GCD of twelve and eighteen is six.

You could list every divisor of both numbers. But there's a two-thousand-year-old shortcut: Euclid's algorithm. The GCD of a and b is the same as the GCD of b, and a modulo b. Keep going, until b becomes zero. Then a is the answer.

Let's try forty-eight and eighteen. Forty-eight modulo eighteen is twelve, so now we have eighteen and twelve. Eighteen modulo twelve is six: twelve and six. Twelve modulo six is zero: six and zero. b is zero, so the GCD is six.

In Java, it's a single line. If b is zero, return a. Otherwise, return gcd of b, and a modulo b. And it's fast: O of log of the smaller number. Even for numbers in the billions, it's done in a few dozen steps.

Then there's the LCM: the least common multiple, the smallest number that both a and b divide. The rule is: a times b, divided by their GCD.

But here's a trap. a times b can overflow before you divide. So divide first. Write a divided by the GCD, then times b. Same answer, no overflow.

You'll use GCD for simplifying fractions, for problems about equal groups, and anywhere two numbers have to line up.

Next, modulo arithmetic. The percent sign gives the remainder. Seventeen modulo five is two.

But here's a Java trap. With a negative number, the result keeps the sign of the left side. So minus seven modulo three is not two. It's minus one. If you need a result that's never negative, add m, and take the modulo again.

Now, why do so many problems say: return the answer modulo ten to the nine plus seven? Because the real answer is huge. It can have hundreds of digits, and no int or long can hold it. So you return only the remainder.

And why that number? Ten to the nine plus seven is a prime. It fits in an int. And two numbers below it, multiplied together, still fit in a long.

The rules are simple. For addition, take the modulo after every add. For multiplication, multiply in long, then take the modulo. Do it at every step, not just at the end. Wait until the end, and the number overflows long before you get there.

Subtraction can go negative, so add m before you take the modulo. And division? You can't just divide under a modulo. Instead, you multiply by the modular inverse. When m is prime, the inverse of b is b to the power m minus two. And to compute a power that big, you need our next tool.

Fast power. Say you need x to the power n. The simple loop multiplies x, n times. That's O of n. And when n is ten to the eighteen, that's never going to finish.

The fast way is called binary exponentiation. The idea: x to the power ten is x to the five, squared. So instead of making n one smaller each time, you cut it in half.

Here's the loop. Start with a result of one. If n is odd, multiply the result by x. Then square x, and halve n. Repeat until n is zero.

Take three to the power thirteen. Thirteen is eight plus four plus one, so the answer is three to the eight, times three to the four, times three. The loop finds exactly those pieces, from the binary digits of thirteen.

Each step halves n, so it's O of log n. Even for n equals ten to the eighteen, that's about sixty steps. And if you need the answer modulo m, take the modulo after every multiply.

Now, a few formulas, and Java math traps.

The sum from one to n is n times n plus one, divided by two. That's O of one, not O of n. It solves problems like the missing number: subtract the sum of the array from the formula, and what's left is the missing number. Just use long when n is big.

Integer division drops the decimal part. Seven divided by two is three. And to round up, for positive numbers, write a plus b minus one, divided by b. You'll use that for things like the number of pages, or trips.

Math dot pow returns a double, not an int. Doubles can't hold big numbers exactly, so for whole number powers, use a loop, or fast power.

And here's the strangest one. Math dot abs of the smallest int is still negative. Minus two point one billion has no positive twin in an int. So if a value can be that small, use long.

So, which tool do you use? Here's the cheat sheet. Pause and screenshot this.

If the problem asks about the digits of a number, use modulo ten, and divide by ten.

If it asks for all divisors, or whether one number is prime, check up to the square root.

If it needs every prime up to n, use the sieve.

If it talks about fractions, equal groups, or the LCM, think GCD.

If it says return the answer modulo ten to the nine plus seven, use long, and take the modulo at every step.

If it needs a huge power, use fast power.

And if it asks for the sum from one to n, use the formula.

Okay, quiz time. Three questions. Pause the video, work out each answer, and then hit play.

Question one. In Java, what does minus seven modulo three print?

Question two. Is one a prime number?

Question three. What's the GCD of forty-eight and eighteen, and how many steps does Euclid's algorithm take?

Ready?

Question one: minus one. In Java, the result keeps the sign of the left side. Add three, and take the modulo again, to get two.

Question two: no. A prime must be greater than one. The smallest prime is two.

Question three: six, in three steps. Forty-eight and eighteen, then eighteen and twelve, then twelve and six, and then the remainder is zero.

How many did you get right? Tell me in the comments: three out of three, two, or one.

Let's recap. Modulo ten and divide by ten take a number apart, digit by digit, in O of log n. Divisors come in pairs, so check up to the square root. The same goes for testing one prime. For every prime up to n, use the Sieve of Eratosthenes, in O of n log log n. For the GCD, use Euclid's algorithm. And for the LCM, divide before you multiply. Under a modulo, take the remainder at every step, and watch out for negative results in Java. And for big powers, use fast power, in O of log n.

Your homework. Solve Count Primes on LeetCode, first with a square root check, then with the sieve, and compare how fast they run. Then tell me in the comments: what's the GCD of one thousand seventy-one and four hundred sixty-two?

Next episode, we cover bit manipulation. AND, OR, XOR, shifts, and the tricks that turn hard problems into one line of code.

And don't forget to subscribe to Compiled Canvas, so you don't miss anything new in tech and the job market. Keep coding, stay consistent, and I'll see you in the next one.