~/problems

Problems

Basics first, then the classics, then company-style assessments. Every problem has tests you run right here; multi-level ones unlock as you go. See the roadmap.

Number theory

Primes, divisors and GCD

Sieve, trial division to sqrt(n), Euclid's algorithm.

Quiz (10) Spot the pattern
Notes

  • Sieve of Eratosthenes, O(n log log n):

    is_p = [True] * (n + 1); is_p[0] = is_p[1] = False
for i in range(2, int(n ** 0.5) + 1):
    if is_p[i]:
        is_p[i*i::i] = [False] * len(range(i*i, n + 1, i))

  • Trial division up to sqrt(n) for factorization. Divisors come in pairs (d, n/d).

  • Euclid: gcd(a, b) = gcd(b, a % b). Then lcm = a // gcd(a, b) * b. math.gcd and math.lcm are built in.

  • Smallest prime factor sieve: factorize any number up to n in O(log n).

7 problems

Advanced & competitive

Number theory Modular arithmetic, primes, matrix powers.

Primes, divisors and GCD

esc