Count Coprime Pairs
HardMathArrayNumber Theory
Description
Given an array of positive integers, return the number of index pairs (i, j) with i < j and gcd(nums[i], nums[j]) = 1.
Examples
Input:
nums = [2,3,4]Output:
2Explanation:
(2,3) and (3,4) are coprime.
Input:
nums = [4,6,8]Output:
0Explanation:
All share factor 2.
Input:
nums = [1,1,1]Output:
3Explanation:
1 is coprime with everything.
Constraints
- •
1 ≤ nums.length ≤ 1000 - •
1 ≤ nums[i] ≤ 10⁵