Added solution in the comment. Thanks to @kunal_singhal & @user0871pc

This question was asked in coding round in one of the companies (Got it on the internet so don't know the company name :D)

Problem: You are given two arrays A and B. For every i in [1,n] find the number of pairs (i,j) such that
gcd(A[i], B[j]) != 1

n = number of elements in both arrays
1 <= n <= 10^5
1 <= Ai, Bi <= 10^6

Sample Testcase:
n = 2
A = 2 4
B = 4 2

Output: 4
// 1 - based indexing
Explanation: pairs (A[1], B[1]), (A[1], B[2]), (A[2], B[1]), (A[2], B[2]) have gcd != 1. So total 4 pairs

So basically we have to count number of pairs (contains one element from both arrays) whose gcd > 1
Been scratching my head for a long time but couldn't find a solution better than O(n^2).
Can any math genius help me in solving this

Thank you in advance.