Программа для расстановки чисел в список пар простых чисел в Python - PullRequest
Новая
       8

Программа для расстановки чисел в список пар простых чисел в Python

1 голос
/ 05 апреля 2020

давайте возьмем 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)

1 Ответ

1 голос
/ 05 апреля 2020

Я предлагаю вам использовать функцию 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]]
...