Maximum Number with this condition satisified

Question

Given an array $A$ of $N$ elements $A[1],A[2],A[3]...A[n]$, I need to find maximum element in the array such that $GCD(G,A[i]) > 1$ for given $G$ and $1\leq i\leq N$.

Example : Let we have $N=6$ and array be $[1,2,3,4,5,4]$ and let $G$ be $2$ then here answer is $4$.

Explanation :

GCD(2,1)=1
GCD(2,2)=2
GCD(2,3)=1
GCD(2,4)=2
GCD(2,5)=1
GCD(2,4)=2

So maximum is $4$ here.

Answer 1

Why don't you just calculate $GCD(G, A[i])$ for all values of $i$?

Edit: If the array $A$ is fixed, then the best path I see is the one you already mentioned, that is, find all prime divisors of $A[i]$ for each $i$. You do not even need the full prime factorisation, only a list of prime numbers dividing each number.

Another optimisation off the top is that you can first sort the array $A$ from largest to smallest and remove duplicates, so that $A[1]> A[2]>A[3]>\dots$.

Now, when you get a number $G$ first check if any prime divisors of $A[i]$ also divide $G$. If one does, then $A[1]$ is the answer. If not, repeat with $A[2]$ and so on.