Number of Different Subsequences GCDs LeetCode solution in Python

1
import math
2

3

4
class Solution:
5
    def countDifferentSubsequenceGCDs(self, nums: List[int]) -> int:
6
        max_n = max(nums) + 1
7
        seen = set(nums)
8

9
        ans = 0
10
        for k in range(1, max_n):  # iterate candidate k
11
            gcd = 0
12
            for multiple in range(
13
                k, max_n, k
14
            ):  # compute gcd of all array multiples of k
15
                if multiple in seen:
16
                    gcd = math.gcd(gcd, multiple)
17
            if gcd == k:  # check the candidate
18
                ans += 1
19
        return ans