[Python] O(nlogn + n*sqrt(V)) beats 100%
Idea\nFirst, sort the array O(nlogn).\nWe maintain a dictionary d where d[v] records the longest subsequence ending with v.\nWhen encountering a new value v, v 
**Idea**\nFirst, sort the array `O(nlogn)`.\nWe maintain a dictionary `d` where `d[v]` records the longest subsequence **ending with v**.\nWhen encountering a new value `v`, `v` can only be appended to those subsequence ending with `v`\'s factors. Thus, we only needs to iterate through `v`\'s factors, which is `O(sqrt(V))`\n\n**Complexity**\n- time: `O(nlogn + n*sqrt(V)), where V is the size of number`\n- space: `O(VN)`\n\n**Python3**\n```\n# factors, O(nlogn + nlogV), V is the size of num in nums\nclass Solution:\n    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:\n        def factors(n):\n            yield 1\n            for i in range(2, int(math.sqrt(n)) + 1):\n                if not n % i:\n                    yield i\n                    if i * i != n:\n                        yield n // i\n                        \n        nums.sort()                        \n        d = {}            \n        for n in nums:\n            for f in factors(n):\n                tmp = d.get(f, []) + [n]\n                d[n] = tmp if len(d.get(n, [])) < len(tmp) else d.get(n, [])\n        return nums and max(d.values(), key=len)\n        # AC: 100 ms, beats 100.00%, 13.9 MB\n```\n\n
['Python']