This is the code. The factorization algorithm is taken from KACTL, same with the Miller-Rabin and with the modmul and the modpow.
My thought process:
If we take each pair and then prime factorize each of the numbers in the pair and then take the union of those prime factors and then for each union, we count the number of primes and if there are $$$n$$$ of those primes in the pairs then, at least one number from each pair will be divisible by that number.
Complexity
Since the prime factorization is $$$O(n^{\frac{1}{4}})$$$, and we are doing $$$O(n)$$$ of them and there are at most 30 prime factors for a number $$$\le 2 \cdot 10^{9}$$$, the complexity is about $$$O(n \cdot n^{\frac{1}{4}})$$$ or $$$O(n^{\frac{5}{4}})$$$. This complexity should suffice for $$$n \le 150,000$$$
Please let me know if there is a section where it is not clear. Thanks for reading the blog.