Math & number theory

Using math to bypass brute force, like finding all primes instantly or shrinking numbers.

The idea

Sieve of Eratosthenes: To find all primes up to N, don't check if each number is prime. Instead, start at 2 (a prime) and cross out all its multiples. Move to the next uncrossed number (3), and cross out its multiples. What's left are primes! Takes O(N log log N).

Euclidean Algorithm (GCD): The greatest common divisor of A and B is the same as the GCD of B and A % B. You can shrink huge numbers in O(log(min(A,B))) time.

Grid from 2 to 30. Click Step.

How it works

# GCD
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Sieve
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for p in range(2, int(n**0.5) + 1):
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
    return [i for i, val in enumerate(is_prime) if val]