用Python编程将数字排列到列表共素数对中

Question

让我们取n=15
我希望它以所有列表都有同素对的方式进行拆分
例如

[[2,3,5,7,11,13],[4,9],[8,15],[1,6],[1,10],[1,12],[1,14]] 

子列表的计数应该是最小的
因为每个子列表都有与其他子列表共素的元素
我试过了，但有一个错误有人能解决这个问题吗

# cook your dish here
import math
def isprime(x):
for i in range(2,(x//2)+1):
if x%i==0:
return False
return True
def ISP(x):
X=[]   
while x% 2 == 0:
X.append(2)
x = x// 2
for i in range(3,x+1,2):
while x % i== 0:
X.append(i)
x = x // i
R=[]
[R.append(x) for x in X if x not in R] 
if len(R)==1:
return True
else:
return False


t=int(input())
for i in range(t):
n=int(input())
R=[]
P=[]
A=[]
for i in range(2,n+1):
if isprime(i):
P.append(i)
elif ISP(i):
if len(A):
for j in A:
if j%i==0 or i%j==0:
N=[2,1]
N.append(i)
R.append(N)
else:
A.append(i)
else:
A.append(i)
else:
N=[2,1]
N.append(i)
R.append(N)
A.append(1)        
P.insert(0,len(P))
A.insert(0,len(A))
R.append(P)
R.append(A)
print(R)

Answer 1

我建议您使用函数math.gcd，并执行以下操作：

from math import gcd
n = 15
groups = []
s = set(range(2, n + 1))
while s:
seeds = [s.pop()]
# append elements to seeds if they are co-prime with all the seeds
for element in s:
if all(gcd(element, e) == 1 for e in seeds):
seeds.append(element)
# remove all seeds from s
s -= set(seeds)
# append seeds to group
groups.append(seeds if len(seeds) > 1 else [1] + seeds)
print(groups)

输出

[[2, 3, 5, 7, 11, 13], [4, 9], [1, 6], [8, 15], [1, 10], [1, 12], [1, 14]]