A billion steps, or 31,623?

Same answer. Math for DSA.

Tap to start →

Stop at √n

To check if n is prime, test divisors only up to its square root.

All primes at once

Cross out multiples of each prime. Everything left is prime.

Euclid's trick

gcd(a, b) = gcd(b, a % b), until b is 0.

Keep numbers small

Answers too big? Take % 1,000,000,007 after every step.

The mistake

In Java, −7 % 3 is −1, not 2. Add the divisor and take % again.

Can you get it?

Tap an answer. The full video explains why.

Cheat sheet

• Prime check: up to √n
• Sieve: cross out multiples
• gcd(a,b) = gcd(b, a%b)
• Mod after every step
• Negative %: add and % again

Want the full lesson?

Free DSA in Java course. Subscribe to Compiled Canvas on YouTube.