求m的两个因子，d1>1和d2>1，其中gcd（d1+d2，m）=1

Question

我试图回答关于共同力量的问题。它需要计算出答案的主要因素

但不知何故，即使在实现了Eratosthenes算法之后，我的代码也显示超出了时间限制。以下是我的代码供参考。如果能提供任何帮助，我将不胜感激

def eratosthenes(n):
    l=[]

    status=[1 for i in range(n+1)]
    for i in range(2,n+1):
        if status[i]:
            if n%i==0:
                l.append(i)
            for j in range(i*i, n+1, i):
                status[j]=0
    # print(l)
    return l

n = int(input())
arr = list(map(int, input().split()))
l1 = [-1 for i in range(n)]
l2 = [-1 for i in range(n)]

for i in range(n):
    primeDivisors= (eratosthenes(arr[I]))
    # print(primeDivisors)
    if len(primeDivisors)<=1:
        continue

    l1[i]=primeDivisors[0]
    l2[i]=primeDivisors[1]


for i in range(n):
    print(l1[i],end=" ")
print()
for i in range(n):
    print(l2[i],end=" ")

问题陈述

给定n个整数a1，a2，…，an

对于每个ai，找到其两个除数d1>；1和d2>；1使得gcd（d1+d2，ai）=1（其中gcd（a，b）是a和b的最大公约数），或者说不存在这样的一对

输入

第一行包含单个整数n（1≤N≤5.⋅10^5）-数组a的大小

第二行包含n个整数a1，a2，…，an（2≤人工智能≤10^7）-阵列a

输出

要加快输出速度，请打印两行，每行有n个整数

第一行和第二行中的第i个整数应为相应的除数d1>；1和d2>；1使得gcd（d1+d2，ai）=1或−1及−1如果没有这样的一对。如果有多个答案，请打印其中任何一个

Answer 1

你使用素数因子是正确的。对于互质p和q（这些素数必须是

gcd(p + q, p*q) = 1

因为如果有一些素数将{}或{}分为{}和{}，它必然会将{}和{}分开，但这与它们是互质相矛盾

不幸的是，即使我们选择素数p和q，我们也无法将此语句扩展到：

gcd(p + q, p^m * q^n * other_prime_powers) = 1

因为other_prime_powers的除数可以除(p + q)，例如gcd(3 + 11 = 14, 3*11*2) != 1。（在我们的例子中，p^m * q^n * other_prime_powers将是A[i]，输入元素，p和q是其大于1的素数因子中的任意两个。）

但是我们可以人工构造一个A[i]的所有素数幂的划分，然后我们可以说

gcd(a*b*c... + x*y*z..., a*b*c...*x*y*z...) = 1

因为我们已经保证A[i]的任何除数，比如说x*y*z...，都不能同时分割分区的一侧

对于每个元素，将其素数幂分为两个任意乘积；如果元素是素数幂，则将其答案设置为-1

从技术上讲，要创建分区，我们只需要找到A[i]的素数幂之一p，然后用p除以A[i]