Recently appeared for microsoft interview for SDE. This is the question asked, I could solve it using brut force (interviewer did not look satisfied so tried to optmize) but couldn't optimize it.

Question:
Given two arrays A and B, for every i ∈[1,N] find the number of pairs(i,j) such that GCD(A[i],B[j])≠1.

Output format:
Output one integer, the answer denoting the total number if pairs satisfying the given condition.

Example:
N=2
A=[2,4]
B=[4,2]
Output: 4

Constraints: 1<=N<=10^5 (N is size of array)
1<=Ai,Bi<=10^6

how to solve/optmize this question.