Гипотеза Гольдбаха в Python

Я попытался написать код, который возвращает одну пару, удовлетворяющую гипотезе Гольдбаха для данного N. Гипотеза утверждает, что каждое четное число больше 4 может быть выражено как сумма двух простых чисел. Функция возвращает пару, которая немного отличается, например, goldbach (34) возвращает (5, 31), а не правильный ответ (3, 31). Точно так же goldbach (38) возвращает (11, 31). Есть идеи, где я здесь ошибаюсь? Я понимаю, что этот код не очень эффективен, однако именно так меня попросили написать код для моего задания.

def eratosthenes(n):
    primes = list (range(2, n+1))
    for i in primes:
        j=2
        while i*j<= primes[-1]:
            if i*j in primes:
                primes.remove(i*j)
            j=j+1
    return primes

def odd_primes(N):
    oddprimes = eratosthenes(N)
    oddprimes.remove(2)
    return(oddprimes)

def goldbach(N):
    x, y = 0, 0
    result = 0
    if N % 2 == 0:
        prime = odd_primes(N)
        while result != N:
            for i in range(len(prime)):
                x = prime[i]
                if result == N: break
                for j in range(len(prime)):
                    y = prime[j]
                    result = x + y
                    if result == N: break 
    return x, y 

Есть ли сценарий, при котором это действительно работает?

Tobias Wilfert 17.12.2018 16:31

@TobiasWilfert не то, что я смог найти!

jemima 17.12.2018 16:55
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
2
6 236
6

Ответы 6

Вы назначаете x перед тем, как разорвать цикл после выполнения вашего условия. Просто инвертируйте ваши строки break в первом цикле for:

def goldbach(N):
    x, y = 0, 0
    result = 0
    if N % 2 == 0:
        prime = odd_primes(N)
        while result != N:
            for i in range(len(prime)):
                if result == N: break  # this line first
                x = prime[i]   # this line after
                for j in range(len(prime)):
                    y = prime[j]
                    result = x + y
                    if result == N: break 
    return x, y 
def eratosthenes(n):
    primes = list (range(2, n+1))
    for i in primes:
        j=2
        while i*j<= primes[-1]:
            if i*j in primes:
                primes.remove(i*j)
            j=j+1
    return primes

def odd_primes(N):
    oddprimes = eratosthenes(N)
    oddprimes.remove(2)
    return(oddprimes)

def goldbach(N):
    x, y = 0, 0
    result = 0
    if N % 2 == 0:
        prime = odd_primes(N)
        while result != N:
            for i in range(len(prime)):
                if result == N: break 
                x = prime[i]
                for j in range(len(prime)):
                    y = prime[j]
                    result = x + y
                    if result == N: break 
    return x, y 

это правильная версия. Когда вы нашли пару, вы устанавливаете x на следующее простое число.

    def isPrime(n):
        for i in range(2,n):
            if n%i == 0:
                return 0
        return 1

    no = int(input("Enter Number: "))

    for i in range(3,no):
        if isPrime(i) == 1:
            for l in range(i,no):
                if isPrime(l) == 1:
                    if no == (i+l):
                        print(i,"+",l," = ",no)

Гипотеза Гольдбаха соблюдается только для четных чисел больше 2, поэтому я улучшаю ответ Панни, чтобы уловить нечетные числа и любое число, меньшее 2.

def isPrime(n):
    for i in range(2,n):
        if n%i == 0:
            return 0
    return 1

def goldbach(no):
  if no%2 !=0 :
    return "Error {} is not an even number ".format(no) 
  elif no <= 2:
    return "Error {} is not greater than 2, Goldbach Conjecture is observed only in even numbers greater than 2".format(no)

  else:
      for i in range(3,no):
          if isPrime(i) == 1:
              for l in range(i,no):
                  if isPrime(l) == 1:
                      if no == (i+l):
                          print(i,"+",l," = ",no)

no = int(input("Enter Even Number greater than 2: "))
goldbach(no)            ```

в чем улучшение?

Muhammad Dyas Yaskur 13.09.2021 02:05

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

Community 13.09.2021 05:17

Можно использовать сито, которое отделяет простые числа 1 (mod 6) от единиц -1 (mod 6), таким образом можно ускорить использование numpy без использования цикла for:

import numpy as np

def sieve(n):
    P5m6 =np.ones((n//6+1), dtype=bool)
    P1m6 =np.ones((n//6+1), dtype=bool)
    for i in range(1,int((n**0.5+1)/6)+1):
        if P5m6[i]:
            P5m6[6*i*i::6*i-1]=[False]
            P1m6[6*i*i-2*i::6*i-1]=[False]
        if P1m6[i]:
            P5m6[6*i*i::6*i+1]=[False]
            P1m6[6*i*i+2*i::6*i+1]=[False]
    return P5m6,P1m6


def goldbach(n):
    P5m6,P1m6=sieve(n)
    nmod6=n%6
    if nmod6==0:
        r=(6*np.nonzero(P5m6[1:n//6]&P1m6[n//6-1:0:-1])[0]+5)[0]
    elif nmod6==2:
        if P5m6[n//6]:
            r=3
        else:
            r=(6*np.nonzero(P1m6[1:(n-6)//12+(n//6-1)%2+1]&P1m6[n//6-1:(n-6)//12:-1])[0]+7)[0]
    elif nmod6==4:
        if P1m6[n//6]:
            r=3
        else:
            r=(6*np.nonzero(P5m6[1:n//12+(n//6)%2+1]&P5m6[n//6:n//12:-1])[0]+5)[0]
    else:
        r=0
    return r,n-r

Разложение Гольдбаха четного числа на пару простых чисел не (всегда) уникально, поэтому вам нужен метод для выбора одного возможного решения (как требуется из вопроса). Естественной возможностью было бы использование функции min / max.

Я не использовал функцию odd_primes (просто срез), а переопределил функцию goldbach, используя комбинаторический подход.

import itertools as it

def eratosthenes(n):
    primes = list (range(2, n+1))
    for p in primes:
        j = 2
        while p*j <= primes[-1]:
            if p*j in primes:
                primes.remove(p*j)
            j += 1
    return primes

def goldbach(n):
    if n % 2 != 0 or n <= 2: raise Exception('Conjecture assumptions not satisfied.')
    ps = eratosthenes(n)[1:]
    # trivial cases to overcome limitations of the combinations
    if n == 4: return [(2, 2)]
    if n == 6: return [(3, 3)]

    return max(it.combinations(ps, 2), key=lambda p: p[1] if sum(p) == n else 0)

for n in range(6, 40, 2):
    print(n, goldbach(n))

Вывод

8 (3, 5)
10 (3, 7)
12 (5, 7)
14 (3, 11)
16 (3, 13)
18 (5, 13)
20 (3, 17)
22 (3, 19)
24 (5, 19)
26 (3, 23)
28 (5, 23)
30 (7, 23)
32 (3, 29)
34 (3, 31)
36 (5, 31)
38 (7, 31)

Другие вопросы по теме