↓Skip to main content

Gcd

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 1071: Greatest Common Divisor of Strings
·2 mins
LeetCode Daily Easy String Gcd Math
LeetCode Problem Solving
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 1979: Find Greatest Common Divisor of Array
·1 min
LeetCode Easy Math Number-Theory Gcd Array
LeetCode 1979 note: find the minimum and maximum, then take their GCD with Euclid’s algorithm