Я попытался написать код, который возвращает одну пару, удовлетворяющую гипотезе Гольдбаха для данного 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
@TobiasWilfert не то, что я смог найти!
Вы назначаете 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) ```
в чем улучшение?
В том виде, в каком оно написано, ваш ответ неясен. Пожалуйста, редактировать, чтобы добавить дополнительную информацию, которая поможет другим понять, как это решает заданный вопрос. Вы можете найти дополнительную информацию о том, как писать хорошие ответы в справочном центре.
Можно использовать сито, которое отделяет простые числа 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)
Есть ли сценарий, при котором это действительно работает?