Number-Theory

LeetCode 4098 note: value’s smallest prime factor p decides everything: the next element is at least value + p, then even numbers step by 2; the left side is feasible iff value - p >= 2 * index

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 4081 note: sieve the primes, then 0/1 knapsack with dp[j] the fewest primes summing to j; adding primes from large to small, a tie gives a smaller first element, so updating on <= yields the lexicographically smallest

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 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 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 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 1627 note: no pairwise GCDs; for each z > threshold, connect all multiples of z, O(n log n) unions in total

LeetCode 3984 note: replacing a composite k by one of its prime factors only helps (more values divisible, smaller k), so try every prime factor of the numbers plus 2, running Kadane once per candidate

LeetCode 3918 note: reverse n, take the range [min, max], and sum primes by trial division; test divisibility with %, never by comparing // with /

LeetCode 2413 note: lcm(2, n), which is n when n is even and 2n when odd

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