Python3 || primes  || T/S: 99% / 52%
Here\'s the intuition:\n- Integers are similar to molecules, and in particular, prime numbers are similar to atoms. When we know the prime composition of each o
Here\'s the intuition:\n- Integers are similar to molecules, and in particular, prime numbers are similar to atoms. When we know the prime composition of each of a pair of integers, we can determine the *gcd* of this pair more efficiently.\n\n- We use a sieve to determine the relevant primes for `nums`.\n-  The details are left to the interested reader.\n```python3 []\nclass Solution:\n\n    def sieve(self, mx_prime: int)-> None:\n        self.primes = [2]\n        not_prime = set()\n\n        for num in range(3, mx_prime, 2):\n            if num in not_prime: continue\n            self.primes.append(num)\n            not_prime|= set(range(num, mx_prime, num))\n        return        \n\n\n    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:\n\n        mx = max(nums) + 1\n        self.sieve(mx)\n\n        ctr = [0] * mx\n        for num in nums: ctr[num] += 1\n\n        for p in self.primes:\n            for j in range((mx-1)//p, 0, -1):\n                ctr[j]+= ctr[j * p]\n\n        for i in range(mx):\n            ctr[i] = comb(ctr[i], 2)\n\n        for p in self.primes:\n            for j in range((mx-1)//p + 1):\n                ctr[j]-= ctr[j * p]\n                \n         acc = list(accumulate(ctr))\n\n        return map(lambda x: bisect_right(acc, x), queries)\n```\n\n[https://leetcode.com/problems/sorted-gcd-pair-queries/submissions/1416221006/](https://leetcode.com/problems/sorted-gcd-pair-queries/submissions/1416221006/)\n\nI could be wrong, but I think that time complexity is *O*(*N* log log *N*) and space complexity is *O*(*N* log log *N*), in which *N* ~ `len(nums)`.
['Python3']