Number of Different Subsequence GCDs

Given an array nums, return the number of different gcd values that can be formed by any non-empty subsequence of nums.

Input Format

nums = array of positive integers

Output Format

count of distinct gcd values over all non-empty subsequences

Constraints

  • 1 <= nums.length <= 10^5; 1 <= nums[i] <= 2 * 10^5

Examples

Example 1:

Input:

nums = [6,10,3]

Output:

5

Explanation:

Possible gcds include 1, 2, 3, 5, and 6.

Example 2:

Input:

nums = [5,15,40,5,6]

Output:

7

Explanation:

Multiple gcd values can be formed by different subsequences.

Loading...
Number of Different Subsequence GCDs - Math