import Mathlib /-! # Largest Component Size By Common Factor You are given an integer array of unique positive integers nums. Consider the following graph: There are nums.length nodes, labeled nums[0] to nums[nums.length - 1], There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1. Return the size of the largest connected component in the graph. ## Constraints - 1 <= nums.length <= 2 * 10^4 - 1 <= nums[i] <= 10^5 - All the values of nums are unique. ## Provided examples - `nums = [4, 6, 15, 35]` → `4` - `nums = [20, 50, 9, 63]` → `2` - `nums = [2, 3, 6, 7, 4, 12, 21, 39]` → `8` ## Synthesized negative examples - invalid input: `nums = []` ([structural] a predicate that admits 1 <= nums.length <= 2 * 10^4. empty where at least one element is required) - invalid input: `nums = [0]` ([structural] a predicate that admits 1 <= nums[i] <= 10^5. zero is below the stated lower bound) - invalid input: `nums = [1, 2, 1]` ([structural] a predicate that admits All the values of nums are unique.. duplicate not adjacent; an adjacent-only uniqueness check accepts it) - `nums = [4, 6, 15, 35]` → `5` is wrong ([structural] answer is not required to be a component size, only an upper bound on all component sizes. no component can contain five nodes, but none contains more) - `nums = [20, 50, 9, 63]` → `3` is wrong ([structural] no component of size 3 exists; soundness omitted. claims a maximum no component reaches) - `nums = [2, 3, 6, 7, 4, 12, 21, 39]` → `7` is wrong ([structural] off-by-one in the computed largest component size. one less than the largest component size) -/ namespace PLargestComponentSizeByCommonFactor abbrev Input := List Nat abbrev Output := Nat /-! ### Specification helpers -/ /-- The graph edge relation: `a` and `b` have a common divisor greater than one. -/ def SharesCommonFactor (a b : Nat) : Prop := 1 < Nat.gcd a b /-- `C` is a connected component of the common-factor graph on the entries of `nums`. -/ def IsConnectedComponent (nums : List Nat) (C : Finset Nat) : Prop := C.Nonempty ∧ (∀ v ∈ C, v ∈ nums) ∧ (∀ a ∈ C, ∀ b ∈ C, Relation.ReflTransGen (fun x y => x ∈ nums ∧ y ∈ nums ∧ SharesCommonFactor x y) a b) ∧ (∀ v ∈ nums, v ∉ C → ∀ w ∈ C, ¬ SharesCommonFactor v w) /-! ### Validity predicate (V) -/ /-- Valid input: `1 ≤ nums.length ≤ 2·10⁴`, every entry in `[1, 10⁵]`, all entries distinct. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 2 * 10 ^ 4 && input.all (fun x => 1 ≤ x && x ≤ 10 ^ 5) && decide input.Nodup /-! ### Ideal specification (P_spec) -/ /-- `result` is the largest cardinality attained by a connected component of the common-factor graph on `input`. -/ def largestComponentSize_spec (input : Input) (result : Output) : Prop := IsGreatest {k | ∃ C : Finset Nat, IsConnectedComponent input C ∧ C.card = k} result /-! ### Decidable specification (P_check) -/ /-- Boolean form of the specification's edge relation. -/ def sharesFactor (a b : Nat) : Bool := decide (1 < Nat.gcd a b) /-- One closure step: every vertex of `nums` adjacent to some reached vertex joins the reached list. -/ def closureStep (nums reached : List Nat) : List Nat := reached ++ nums.filter (fun w => reached.any (fun x => sharesFactor x w)) /-- The vertices of `nums` reachable from the already reached ones after `fuel` closure steps. -/ def reachClosure (nums : List Nat) (fuel : Nat) (reached : List Nat) : List Nat := match fuel with | 0 => reached | fuel + 1 => reachClosure nums fuel (closureStep nums reached) /-- The connected component of `v` as the finite set of vertices reachable from it. -/ def componentOf (nums : List Nat) (v : Nat) : Finset Nat := (reachClosure nums nums.length [v]).toFinset /-- Executable checker for `largestComponentSize_spec` over the vertex reachability classes. -/ def largestComponentSize_check (input : Input) (result : Output) : Bool := decide ((∃ v ∈ input, (componentOf input v).card = result) ∧ (∀ v ∈ input, (componentOf input v).card ≤ result)) def wxStep (nums : List Nat) (reached : Finset Nat) : Finset Nat := reached ∪ nums.toFinset.filter (fun w => ∃ x ∈ reached, sharesFactor x w = true) lemma wx_closureStep_toFinset (nums reached : List Nat) : (closureStep nums reached).toFinset = wxStep nums reached.toFinset := by ext y simp [closureStep, wxStep, List.any_eq_true] lemma wx_reach_succ_list (nums reached : List Nat) (m : Nat) : reachClosure nums (m + 1) reached = closureStep nums (reachClosure nums m reached) := by induction m generalizing reached with | zero => rfl | succ m ih => change reachClosure nums (m + 1) (closureStep nums reached) = closureStep nums (reachClosure nums m (closureStep nums reached)) exact ih (closureStep nums reached) lemma wx_reach_succ_finset (nums reached : List Nat) (m : Nat) : (reachClosure nums (m + 1) reached).toFinset = wxStep nums (reachClosure nums m reached).toFinset := by rw [wx_reach_succ_list, wx_closureStep_toFinset] lemma wx_reach_mono_succ (nums reached : List Nat) (m : Nat) : (reachClosure nums m reached).toFinset ⊆ (reachClosure nums (m + 1) reached).toFinset := by rw [wx_reach_succ_finset] intro x hx exact Finset.mem_union_left _ hx lemma wx_closureStep_subset_nums (nums reached : List Nat) (h : reached ⊆ nums) : closureStep nums reached ⊆ nums := by intro x hx simp only [closureStep, List.mem_append, List.mem_filter] at hx rcases hx with hx | ⟨hx, _⟩ · exact h hx · exact hx lemma wx_reach_subset_nums (nums reached : List Nat) (h : reached ⊆ nums) (m : Nat) : reachClosure nums m reached ⊆ nums := by induction m generalizing reached with | zero => exact h | succ m ih => simp only [reachClosure] exact ih (closureStep nums reached) (wx_closureStep_subset_nums nums reached h) lemma wx_reach_subset_finset (nums : List Nat) (v : Nat) (hv : v ∈ nums) (m : Nat) : (reachClosure nums m [v]).toFinset ⊆ nums.toFinset := by intro x hx rw [List.mem_toFinset] at hx ⊢ exact wx_reach_subset_nums nums [v] (by simpa using hv) m hx lemma wx_reach_card_stable (nums : List Nat) (v : Nat) (hv : v ∈ nums) : (reachClosure nums (nums.length + 1) [v]).toFinset.card = (reachClosure nums nums.length [v]).toFinset.card := by let f : Nat → Nat := fun m => (reachClosure nums m [v]).toFinset.card have hfmono : Monotone f := monotone_nat_of_le_succ (fun m => Finset.card_le_card (wx_reach_mono_succ nums [v] m)) have hfb : ∀ m, f m ≤ nums.length := by intro m exact (Finset.card_le_card (wx_reach_subset_finset nums v hv m)).trans nums.toFinset_card_le have hfstab : ∀ m, f m = f (m + 1) → f (m + 1) = f (m + 2) := by intro m hm have hset : (reachClosure nums m [v]).toFinset = (reachClosure nums (m + 1) [v]).toFinset := Finset.eq_of_subset_of_card_le (wx_reach_mono_succ nums [v] m) (by simpa only [f] using hm.ge) have hset' : (reachClosure nums (m + 1) [v]).toFinset = (reachClosure nums (m + 2) [v]).toFinset := by calc (reachClosure nums (m + 1) [v]).toFinset = wxStep nums (reachClosure nums m [v]).toFinset := wx_reach_succ_finset nums [v] m _ = wxStep nums (reachClosure nums (m + 1) [v]).toFinset := congrArg (wxStep nums) hset _ = (reachClosure nums (m + 2) [v]).toFinset := by simpa [Nat.add_assoc] using (wx_reach_succ_finset nums [v] (m + 1)).symm exact congrArg Finset.card hset' have hs := Nat.stabilises_of_monotone (f := f) (b := nums.length) (n := nums.length + 1) hfmono hfb hfstab (by omega) simpa only [f] using hs lemma wx_closed (nums : List Nat) (v : Nat) (hv : v ∈ nums) : ∀ x ∈ componentOf nums v, ∀ y ∈ nums, sharesFactor x y = true → y ∈ componentOf nums v := by intro x hx y hy hxy change x ∈ (reachClosure nums nums.length [v]).toFinset at hx change y ∈ (reachClosure nums nums.length [v]).toFinset have hynext : y ∈ (reachClosure nums (nums.length + 1) [v]).toFinset := by rw [wx_reach_succ_finset] exact Finset.mem_union_right _ (Finset.mem_filter.mpr ⟨List.mem_toFinset.mpr hy, ⟨x, hx, hxy⟩⟩) have hcard := wx_reach_card_stable nums v hv have hset : (reachClosure nums nums.length [v]).toFinset = (reachClosure nums (nums.length + 1) [v]).toFinset := Finset.eq_of_subset_of_card_le (wx_reach_mono_succ nums [v] nums.length) hcard.le simpa only [hset] using hynext lemma wx_sharesFactor_true {a b : Nat} : sharesFactor a b = true ↔ SharesCommonFactor a b := by simp [sharesFactor, SharesCommonFactor] lemma wx_shares_symm {a b : Nat} (h : SharesCommonFactor a b) : SharesCommonFactor b a := by simpa only [SharesCommonFactor, Nat.gcd_comm] using h lemma wx_closureStep_mem (nums reached : List Nat) (z : Nat) : z ∈ closureStep nums reached ↔ z ∈ reached ∨ (z ∈ nums ∧ ∃ x ∈ reached, SharesCommonFactor x z) := by simp only [closureStep, List.mem_append, List.mem_filter, List.any_eq_true, wx_sharesFactor_true] lemma wx_reachClosure_preserve (nums : List Nat) (fuel : Nat) (reached : List Nat) (P : Nat → Prop) (h₀ : ∀ x ∈ reached, P x) (hs : ∀ x, P x → ∀ y ∈ nums, SharesCommonFactor x y → P y) : ∀ z ∈ reachClosure nums fuel reached, P z := by induction fuel generalizing reached with | zero => intro z hz exact h₀ z (by simpa only [reachClosure] using hz) | succ fuel ih => intro z hz have hz' : z ∈ reachClosure nums fuel (closureStep nums reached) := by simpa only [reachClosure] using hz apply ih (closureStep nums reached) · intro y hy rcases (wx_closureStep_mem nums reached y).mp hy with hy | ⟨hyn, x, hxr, hxy⟩ · exact h₀ y hy · exact hs x (h₀ x hxr) y hyn hxy · exact hz' lemma wx_reachClosure_contains (nums : List Nat) (fuel : Nat) (reached : List Nat) {x : Nat} (hx : x ∈ reached) : x ∈ reachClosure nums fuel reached := by induction fuel generalizing reached with | zero => simpa only [reachClosure] using hx | succ fuel ih => have hx' : x ∈ closureStep nums reached := by exact (wx_closureStep_mem nums reached x).mpr (Or.inl hx) simpa only [reachClosure] using ih (closureStep nums reached) hx' lemma wx_component_seed (nums : List Nat) (v : Nat) : v ∈ componentOf nums v := by unfold componentOf simp only [List.mem_toFinset] exact wx_reachClosure_contains nums nums.length [v] (by simp) lemma wx_component_mem_nums (nums : List Nat) {v x : Nat} (hv : v ∈ nums) (hx : x ∈ componentOf nums v) : x ∈ nums := by unfold componentOf at hx simp only [List.mem_toFinset] at hx exact wx_reachClosure_preserve nums nums.length [v] (fun z => z ∈ nums) (by intro z hz simp only [List.mem_singleton] at hz subst z exact hv) (by intro a ha b hb hab exact hb) x hx lemma wx_component_reachable (nums : List Nat) {v x : Nat} (hv : v ∈ nums) (hx : x ∈ componentOf nums v) : Relation.ReflTransGen (fun a b => a ∈ nums ∧ b ∈ nums ∧ SharesCommonFactor a b) v x := by unfold componentOf at hx simp only [List.mem_toFinset] at hx have h := wx_reachClosure_preserve nums nums.length [v] (fun z => z ∈ nums ∧ Relation.ReflTransGen (fun a b => a ∈ nums ∧ b ∈ nums ∧ SharesCommonFactor a b) v z) (by intro z hz simp only [List.mem_singleton] at hz subst z exact ⟨hv, Relation.ReflTransGen.refl⟩) (by intro a ha b hb hab exact ⟨hb, ha.2.tail ⟨ha.1, hb, hab⟩⟩) x hx exact h.2 lemma wx_path_mem_component (closed : ∀ (nums : List Nat) (v : Nat), v ∈ nums → ∀ x ∈ componentOf nums v, ∀ y ∈ nums, sharesFactor x y = true → y ∈ componentOf nums v) (nums : List Nat) {v x : Nat} (hv : v ∈ nums) (h : Relation.ReflTransGen (fun a b => a ∈ nums ∧ b ∈ nums ∧ SharesCommonFactor a b) v x) : x ∈ componentOf nums v := by induction h with | refl => exact wx_component_seed nums v | tail hab hbc ih => exact closed nums v hv _ ih _ hbc.2.1 (wx_sharesFactor_true.mpr hbc.2.2) lemma wx_reachable_symm (nums : List Nat) {a b : Nat} (h : Relation.ReflTransGen (fun x y => x ∈ nums ∧ y ∈ nums ∧ SharesCommonFactor x y) a b) : Relation.ReflTransGen (fun x y => x ∈ nums ∧ y ∈ nums ∧ SharesCommonFactor x y) b a := by induction h with | refl => exact Relation.ReflTransGen.refl | tail hab hbc ih => exact ih.head ⟨hbc.2.1, hbc.1, wx_shares_symm hbc.2.2⟩ lemma wx_components (closed : ∀ (nums : List Nat) (v : Nat), v ∈ nums → ∀ x ∈ componentOf nums v, ∀ y ∈ nums, sharesFactor x y = true → y ∈ componentOf nums v) (nums : List Nat) (C : Finset Nat) : IsConnectedComponent nums C ↔ ∃ v ∈ nums, componentOf nums v = C := by constructor · rintro ⟨hne, hvert, hconn, hmax⟩ rcases hne with ⟨v, hvC⟩ have hvn : v ∈ nums := hvert v hvC refine ⟨v, hvn, Finset.ext ?_⟩ intro y constructor · intro hy unfold componentOf at hy simp only [List.mem_toFinset] at hy exact wx_reachClosure_preserve nums nums.length [v] (fun z => z ∈ C) (by intro z hz simp only [List.mem_singleton] at hz subst z exact hvC) (by intro a ha b hb hab by_contra hbn exact (hmax b hb hbn a ha) (wx_shares_symm hab)) y hy · intro hy exact wx_path_mem_component closed nums hvn (hconn v hvC y hy) · rintro ⟨v, hvn, hC⟩ subst C refine ⟨⟨v, wx_component_seed nums v⟩, ?_, ?_, ?_⟩ · intro x hx exact wx_component_mem_nums nums hvn hx · intro a ha b hb exact (wx_reachable_symm nums (wx_component_reachable nums hvn ha)).trans (wx_component_reachable nums hvn hb) · intro y hyn hyout w hw hyw apply hyout exact closed nums v hvn w hw y hyn (wx_sharesFactor_true.mpr (wx_shares_symm hyw)) lemma wx_finish (bridge : ∀ (nums : List Nat) (C : Finset Nat), IsConnectedComponent nums C ↔ ∃ v ∈ nums, componentOf nums v = C) (input : Input) (result : Output) : largestComponentSize_check input result ↔ largestComponentSize_spec input result := by have hs (k : Nat) : (∃ C : Finset Nat, IsConnectedComponent input C ∧ C.card = k) ↔ ∃ v ∈ input, (componentOf input v).card = k := by constructor · rintro ⟨C, hC, hk⟩ obtain ⟨v, hv, rfl⟩ := (bridge input C).mp hC exact ⟨v, hv, hk⟩ · rintro ⟨v, hv, hk⟩ exact ⟨componentOf input v, (bridge input _).mpr ⟨v, hv, rfl⟩, hk⟩ simp only [largestComponentSize_check, decide_eq_true_eq, largestComponentSize_spec, IsGreatest, mem_upperBounds, Set.mem_setOf_eq, hs] grind only [] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem largestComponentSize_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : largestComponentSize_check input result ↔ largestComponentSize_spec input result := by exact wx_finish (wx_components wx_closed) input result /-! ### Implementation helpers -/ /-- Removes every occurrence of the divisor `d` from the positive number `n`. -/ def stripFactor (d n : Nat) : Nat := if hn : 0 < n then if hd : 1 < d then if n % d = 0 then stripFactor d (n / d) else n else n else n termination_by n decreasing_by exact Nat.div_lt_self hn hd /-- Returns the distinct prime factors of `n` by trial division up to its square root. -/ def distinctPrimeFactors (n : Nat) : List Nat := let step := fun (state : List Nat × Nat) (d : Nat) => let (factors, remaining) := state if remaining % d = 0 then (d :: factors, stripFactor d remaining) else state let found := ((List.range (Nat.sqrt n + 1)).drop 2).foldl step ([], n) let factors := found.1.reverse if 1 < found.2 then factors ++ [found.2] else factors /-- Adds `n` to the bucket of the prime `p`. -/ def addNumberToPrimeBucket (primeToNums : Array (List Nat)) (p n : Nat) : Array (List Nat) := if h : p < primeToNums.size then primeToNums.set p (n :: primeToNums[p]'h) h else primeToNums /-- Adds `n` to the bucket of every one of its distinct prime factors. -/ def addNumberToPrimeBuckets (primeToNums : Array (List Nat)) (n : Nat) : Array (List Nat) := (distinctPrimeFactors n).foldl (fun current p => addNumberToPrimeBucket current p n) primeToNums /-- Builds the direct-indexed map from each prime to the input numbers divisible by it. -/ def buildPrimeToNums (nums : List Nat) : Array (List Nat) := let greatest := nums.foldl (fun largest n => max largest n) 0 nums.foldl addNumberToPrimeBuckets (Array.replicate (greatest + 1) ([] : List Nat)) /-- Lists the indices whose prime buckets contain at least one number. -/ def primesWithNumbers (primeToNums : Array (List Nat)) : List Nat := (List.range primeToNums.size).filter (fun p => if h : p < primeToNums.size then match primeToNums[p]'h with | [] => false | _ :: _ => true else false) /-- Marks every listed value as unvisited in a boolean array. -/ def markValues (marks : Array Bool) (values : List Nat) : Array Bool := values.foldl (fun current value => if h : value < current.size then current.set value true h else current) marks /-- The mutable search state for one prime-factor component traversal. -/ structure ComponentState where size : Nat remainingNums : Nat remainingPrimes : Nat unvisitedNums : Array Bool unvisitedPrimes : Array Bool /-- Explores one component by FIFO search over alternating number and prime vertices. -/ def exploreComponent (primeToNums : Array (List Nat)) (state : ComponentState) (numFrontier : Array Nat) (numHead : Nat) (primeFrontier : Array Nat) (primeHead : Nat) : ComponentState := if hn : numHead < numFrontier.size then let n := numFrontier[numHead]'hn if hx : n < state.unvisitedNums.size then if state.unvisitedNums[n]'hx then if hr : 0 < state.remainingNums then let freshPrimes := (distinctPrimeFactors n).filter (fun p => if hp : p < state.unvisitedPrimes.size then state.unvisitedPrimes[p]'hp else false) let primeFrontier' := freshPrimes.foldl (fun frontier p => frontier.push p) primeFrontier exploreComponent primeToNums { state with size := state.size + 1, remainingNums := state.remainingNums - 1, unvisitedNums := state.unvisitedNums.set n false hx } numFrontier (numHead + 1) primeFrontier' primeHead else exploreComponent primeToNums state numFrontier (numHead + 1) primeFrontier primeHead else exploreComponent primeToNums state numFrontier (numHead + 1) primeFrontier primeHead else exploreComponent primeToNums state numFrontier (numHead + 1) primeFrontier primeHead else if hp : primeHead < primeFrontier.size then let p := primeFrontier[primeHead]'hp if hq : p < state.unvisitedPrimes.size then if state.unvisitedPrimes[p]'hq then if hr : 0 < state.remainingPrimes then let bucket := if hb : p < primeToNums.size then primeToNums[p]'hb else [] let freshNums := bucket.filter (fun n => if hx : n < state.unvisitedNums.size then state.unvisitedNums[n]'hx else false) let numFrontier' := freshNums.foldl (fun frontier n => frontier.push n) numFrontier exploreComponent primeToNums { state with remainingPrimes := state.remainingPrimes - 1, unvisitedPrimes := state.unvisitedPrimes.set p false hq } numFrontier' numHead primeFrontier (primeHead + 1) else exploreComponent primeToNums state numFrontier numHead primeFrontier (primeHead + 1) else exploreComponent primeToNums state numFrontier numHead primeFrontier (primeHead + 1) else exploreComponent primeToNums state numFrontier numHead primeFrontier (primeHead + 1) else state termination_by (state.remainingNums + state.remainingPrimes, (numFrontier.size - numHead) + (primeFrontier.size - primeHead)) decreasing_by all_goals first | (apply Prod.Lex.left; omega) | (apply Prod.Lex.right; omega) /-- Finds every still-unvisited component reachable from the remaining starting numbers. -/ def largestFromStarts (primeToNums : Array (List Nat)) (starts : List Nat) (state : ComponentState) (best : Nat) : Nat := match starts with | [] => best | n :: rest => let nIsUnvisited := if h : n < state.unvisitedNums.size then state.unvisitedNums[n]'h else false if nIsUnvisited then let found := exploreComponent primeToNums { state with size := 0 } #[n] 0 (#[] : Array Nat) 0 largestFromStarts primeToNums rest found (max best found.size) else largestFromStarts primeToNums rest state best /-! ### Main algorithm (impl) -/ /-- Computes the largest component by prime-factor BFS over the number-prime incidence graph. -/ def computeLargestComponentSize (input : Input) : Output := let primeToNums := buildPrimeToNums input let primes := primesWithNumbers primeToNums let initialState := { size := 0, remainingNums := input.length, remainingPrimes := primes.length, unvisitedNums := markValues (Array.replicate primeToNums.size false) input, unvisitedPrimes := markValues (Array.replicate primeToNums.size false) primes } largestFromStarts primeToNums input initialState 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem computeLargestComponentSize_correct (input : Input) (h : isValidInput input) : largestComponentSize_spec input (computeLargestComponentSize input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [4, 6, 15, 35] #guard isValidInput [20, 50, 9, 63] #guard isValidInput [2, 3, 6, 7, 4, 12, 21, 39] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [0]) #guard !(isValidInput [1, 2, 1]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard largestComponentSize_check [4, 6, 15, 35] 4 #guard largestComponentSize_check [20, 50, 9, 63] 2 #guard largestComponentSize_check [2, 3, 6, 7, 4, 12, 21, 39] 8 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(largestComponentSize_check [4, 6, 15, 35] 5) #guard !(largestComponentSize_check [20, 50, 9, 63] 3) #guard !(largestComponentSize_check [2, 3, 6, 7, 4, 12, 21, 39] 7) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard computeLargestComponentSize [4, 6, 15, 35] == 4 #guard computeLargestComponentSize [20, 50, 9, 63] == 2 #guard computeLargestComponentSize [2, 3, 6, 7, 4, 12, 21, 39] == 8 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard largestComponentSize_check [4, 6, 15, 35] (computeLargestComponentSize [4, 6, 15, 35]) #guard largestComponentSize_check [20, 50, 9, 63] (computeLargestComponentSize [20, 50, 9, 63]) #guard largestComponentSize_check [2, 3, 6, 7, 4, 12, 21, 39] (computeLargestComponentSize [2, 3, 6, 7, 4, 12, 21, 39]) end PLargestComponentSizeByCommonFactor