↓Skip to main content

Sieve

Number Theory
·6 mins
Algorithm Math Number-Theory Prime Sieve Union-Find Gcd
GCD, primality tests, the sieve of Eratosthenes / linear sieve / smallest prime factor (SPF), connecting numbers by prime factors with Union-Find, and splitting an array by the last occurrence of prime factors
LeetCode 2584: Split the Array to Make Coprime Products
·3 mins
LeetCode Hard Math Number-Theory Sieve Hash-Table Array
LeetCode 2584 note: coprime products ⇔ no prime factor in both parts; record each prime’s last index, extend reach left to right, and split after i when reach == i
LeetCode 2761: Prime Pairs With Target Sum
·2 mins
LeetCode Medium Math Number-Theory Sieve Enumeration Array
LeetCode 2761 note: sieve primes below n, then try x up to n / 2; when x and n - x are both prime, they form a pair
LeetCode 2523: Closest Prime Numbers in Range
·2 mins
LeetCode Medium Math Number-Theory Sieve Array
LeetCode 2523 note: sieve the primes in range, since only adjacent primes can be closest; or trial-divide rightward from left and stop at the first twin primes with gap 2
LeetCode 1998: GCD Sort of an Array
·3 mins
LeetCode Hard Math Number-Theory Union-Find Sieve Sorting Array
LeetCode 1998 note: numbers in one component can be permuted freely; union each number with its prime factors via SPF, and the array sorts iff each position’s old and new values share a group
LeetCode 2709: Greatest Common Divisor Traversal
·3 mins
LeetCode Hard Math Number-Theory Union-Find Sieve Gcd Array
LeetCode 2709 note: every pair of indices connects ⇔ one component; factor with SPF and union each number with its prime factors in Union-Find, treating 1 specially
LeetCode 3618: Split Array by Prime Indices
·2 mins
LeetCode Medium Math Number-Theory Sieve Array
LeetCode 3618 note: primality is about the index; a sieve of Eratosthenes marks all of 0..n-1 at once, faster than trial division per index