↓快轉到主要內容

Sieve

Number Theory 數論
·4 分鐘
演算法 Math Number-Theory Prime Sieve Union-Find Gcd
GCD、判斷質數、埃氏篩 / 線性篩 / 最小質因數（SPF）、質因數分解後用 Union-Find 連起來，以及用質因數的最後出現位置切陣列
LeetCode 2584: Split the Array to Make Coprime Products
·2 分鐘
LeetCode Hard Math Number-Theory Sieve Hash-Table Array
LeetCode 2584 解題筆記：兩段乘積互質 ⇔ 沒有質因數同時出現在兩段；記下每個質因數最後出現的 index，從左往右擴張 reach，reach == i 時就能在 i 後面切
LeetCode 2761: Prime Pairs With Target Sum
·1 分鐘
LeetCode Medium Math Number-Theory Sieve Enumeration Array
LeetCode 2761 解題筆記：篩出 < n 的質數，x 從小到大、只看到 n / 2，x 和 n - x 都是質數就是一對
LeetCode 2523: Closest Prime Numbers in Range
·1 分鐘
LeetCode Medium Math Number-Theory Sieve Array
LeetCode 2523 解題筆記：篩出範圍內的質數，相鄰的兩個質數才可能是最接近的；也可以從 left 往右試除，找到差是 2 的雙生質數就停
LeetCode 1998: GCD Sort of an Array
·2 分鐘
LeetCode Hard Math Number-Theory Union-Find Sieve Sorting Array
LeetCode 1998 解題筆記：同一個連通塊裡的數可以任意交換；用 SPF 把數字跟質因數合併，排序後每個位置的新舊數字在同一組就能排好
LeetCode 2709: Greatest Common Divisor Traversal
·2 分鐘
LeetCode Hard Math Number-Theory Union-Find Sieve Gcd Array
LeetCode 2709 解題筆記：任兩個 index 都能互通 ⇔ 全部在同一個連通塊；用 SPF 分解質因數，數字跟它的質因數在 Union-Find 裡合併；1 要特別處理
LeetCode 3618: Split Array by Prime Indices
·1 分鐘
LeetCode Medium Math Number-Theory Sieve Array
LeetCode 3618 解題筆記：判斷的是 index 是不是質數；用埃氏篩一次算出 0..n-1 哪些是質數，比每個 index 試除快