Gcd maximum and amount

Question

You are given two arrays: A and B. Each of them contains "N" elements each. Select a pair of elements that: X belongs to array A

Y belongs to the array B GCD (X, Y) - the maximum of all pairs (X, Y).

This is a question from Hackerrank weekcodeof 34.

from fractions import gcd

from itertools import product
n = int(input().strip()) #two arrays of equal length
A = set(map(int, input().strip().split(' '))) #array1
B = set(map(int, input().strip().split(' '))) # arry2
output_sum=[]
output_GCD=[]
c=list(product(A,B))
for i in c:

    temp1=i[0]
    temp2=i[1]

    sum_two=temp1+temp2

    temp3=gcd(temp1,temp2)
    output_GCD.append(temp3)
    output_sum.append(temp1+temp2)
temp=[]
for i in range(len(output_GCD)):
  if(output_GCD[i]==max(output_GCD)):
    temp.append(output_sum[i])
print(max(temp))

This solution works for small conditions, and I got the time for most test cases, please help me how to improve my solution.

Answer 1

You can calculate all the dividers a_divisorsfor an array Aas follows:

# it is not real python-code, just ideas of algorithm
count = {}
for (i : A): 
  count[i]++

a_divisors = {}
for (i : range(1, 10^6)):
  for (j = i * i; j <= 10^6; j += i):
    if j in count.keys():
      a_divisors[i] = 1

b_divisors B

:

5
3 1 4 2 8
5 2 12 8 3

:

a: 1, 2, 3, 4, 8
b: 1, 2, 3, 4, 5, 6, 8, 12

: 4

gcd(a, b) = 4, 1 A, divisor 4 1 B: 8 + 12 = 16

Answer 2

A B Set ( )

def maximumGcdAndSum(A, B):
    A = set(A)
    B = set(B)
    max_nbr = max(max(A), max(B))
    i = max_nbr

    while i > 0:  # for each i starting from max number
        i_pow = i  # i, i^2, i^3, i^4, ...
        maxa = maxb = 0

        while i_pow <= max_nbr:  # '<=' is a must here
            if i_pow in A:
                maxa = i_pow  # get the max from power list which devides A
            if i_pow in B:
                maxb = i_pow  # get the max from power list which devides B
            i_pow += i
        if maxa and maxb:
            return maxa + maxb  # if both found, stop algorithm
        i -= 1

    return 0