Проверьте, можно ли разделить число на простые разбиения

Question

Может ли кто-нибудь решить эту проблему на Python?

Положительное целое число m может быть разделено на простые числа, если оно может быть записано как p + q, где p> 0, q> 0 и оба p и q простые.числа.

Напишите функцию Python, которая принимает целое число m в качестве входных данных и возвращает True, если m можно разбить на простые числа, и False в противном случае.

Попробовал это, но не работает для всех тестовых случаев,например, он должен вернуть True для 3432, он возвращает False.

def partition(num):
    primelist=[]
    for i in range(2,num + 1):
        for p in range(2,i):
            if (i % p) == 0:
                break
        else:
            primelist.append(i)


    for x in primelist:
        y= num-x
        for z in range(2,y):
            if y%z == 0:
                return False

        return True

Answer 1

Альтернативный подход, который пытается уменьшить количество необходимого кода:

def primepartition(m):
    if m > 3:
        for number in range(m // 2, m - 1):
            difference = m - number

            for psuedoprime in range(2, int(number ** 0.5) + 1):
                if number % psuedoprime == 0 or difference > psuedoprime and difference % psuedoprime == 0:
                    break
            else:  # no break
                return number, difference  # as good a non-False result as any other...

    return False

Answer 2

Код, приведенный ниже, может дать правильный вывод.

def factors(n):
    factorslist = []
    for i in range(1, n+1, 1):
        if n % i == 0:
            factorslist.append(i)
    return(factorslist)    

def prime(n):
    if factors(n) == [1, n] and n > 1:
        return(True)

def primelist(n):
    primenolist = []
    for i in range(1, n+1, 1):
        if prime(i) == True:
            primenolist.append(i)
    return(primenolist)

def primepartition(m):
    if m > 0:
        primenolist = primelist(m)
        checklist = []
        for p in primenolist:
            q = m - p
            if q in primenolist and p > 0 and q > 0:
                checklist.append((p,q))
        if len(checklist) > 0:
            return(True)
        else:
            return(False)
    else:
        return(False)

Answer 3

окончательное решение, которое я получил:

def primepartition(m):
    primelist=[]
    if m<0:
        return False
    else:
        for i in range(2,m + 1):
            for p in range(2,i):
                if (i % p) == 0:
                    break
            else:
                primelist.append(i)

        for x in primelist:
            y= m-x
            if y in primelist:
                return True
        return False

Answer 4

Небольшое изменение вашего кода:

def primepartition0(m):
    primelist=[]
    if m<0:
        return False
    else:
        for i in range(2,m + 1):
            for p in range(2,i):
                if (i % p) == 0:
                    break
            else:
                primelist.append(i)

        for x in primelist:
            for y in primelist:
                if x != y and x+y == m:
                    return True
        return False   

Answer 5

Ошибка заключается во втором цикле for.Вы просматриваете возможные простые числа x и хотите проверить, что y = num - x также простое число.

Ошибка в вашей логике заключается в том, что во втором цикле for, если первый элемент в цикле y = num - x не простое число, оно вернет False, не проверяя другие возможные значения.

Вы можете исправить это, переместив оператор return False из одного цикла, но так как вы уже сгенерировалисписок простых чисел меньше num, primelist (а так как y = num - x, (если простое y существует) будет в этом списке), вы можете просто проверить членство в списке:

    for x in primelist:
        y= num-x
        # Note: num = x + y, thus need only check y prime
        if y in primelist:
            return True
        # If no such y is prime, not possible
        else:
            return False

Примечание: Я бы посоветовал сделать логику вашего скрипта более модульной, разделив генератор простых списков на его собственную функцию:

def partition(num):
    """
    Return True if there exist primes x,y such that num = x + y.
    Else return False.
    """
    primelist = primes(num)
    for x in primelist:
        y= num-x
        # Note: num = x + y, thus need only check y prime
        if y in primelist:
            return True
    # If no such y is prime, not possible
    else:
        return False

def primes(num):
    """Return list of all primes less than num."""
    primelist=[]
    for i in range(2,num + 1):
        for p in range(2,i):
            if (i % p) == 0:
                break
        else:
            primelist.append(i)
    return primelist