思路：

正常的话，遇到求公因数的问题，肯定是使用辗转相除法，来求公因数。但是这里的数据规模太大，正常的第三个测试点就会超时。

其实这里只要比较两个数有没有公因子就行，所有我们可以想到来求每个数的质因子就可以，然后对比哪些数有共同的质因子。

首先我们可以通过借助埃氏筛的思想，来快速求一个数的最小质因子。这样的好处是我们可以避免重复计算质因子。

arr_Max = max(arr)
spf = [0] * (arr_Max + 1)
for i in range(2, arr_Max + 1):
    if spf[i] == 0:
        spf[i] = i
    for j in range(i * i, arr_Max + 1, i):
        if spf[j] == 0:
            spf[j] = i

然后就是求每个数的所有质因子，这样后面才可以比较。

def get_prime_factor(n):
    factors = []
    if n == 1:
        return factors
    while n != 1:
        factor = spf[n]
        factors.append(factor)
        while n % factor == 0:
            n = n // factor
    return factors

然后我们为了方便寻找有相同质因子的数，并且我们求的结果是最小的索引下标，所以我们可以转换思路使用字典将有相同质因子的下标存储起来，然后查找最小的小标组合。

dict = {}
# 查询每个数的质因子列表，然后将列表内的所有质因子作为字典的key，value存储下标值
for i in range(N):
    for factor in get_prime_factor(arr[i]):
        if factor in dict:
            dict[factor].append(i)
        else:
            dict[factor] = [i]
left = 10e6 + 10
right = 0

# 查找最小的下标组合
for k, v in dict.items():
    if len(v) >= 2 and left >= v[0]:
        if left == v[0]:
            right = min(right, v[1])
        else:
            left = v[0]
            right = v[1]

最终完整代码：
 

N = int(input())
arr = list(map(int, input().split()))
# 先预处理最小质数因子表
arr_Max = max(arr)
spf = [0] * (arr_Max + 1)
# 如果我们要确定两个数有没有公共因子 我们只需要比较有没有相同的质因子就可以
factors_index = {}
for i in range(2, arr_Max + 1):
    if spf[i] == 0:
        spf[i] = i
    for j in range(i * i, arr_Max + 1, i):
        if spf[j] == 0:
            spf[j] = i


# 这样spf[i]就代表了i这个数的最小质数因子
def get_prime_factor(n):
    factors = []
    if n == 1:
        return factors
    while n != 1:
        factor = spf[n]
        factors.append(factor)
        while n % factor == 0:
            n = n // factor
    return factors


dict = {}
for i in range(N):
    for factor in get_prime_factor(arr[i]):
        if factor in dict:
            dict[factor].append(i)
        else:
            dict[factor] = [i]
left = 10e6 + 10
right = 0

for k, v in dict.items():
    if len(v) >= 2 and left >= v[0]:
        if left == v[0]:
            right = min(right, v[1])
        else:
            left = v[0]
            right = v[1]
print(f'{left + 1} {right + 1}')