Сумма простых чисел
У меня есть упражнение:
Напишите программу, которая берет на вход число n и выводит все случаи простых чисел, сумма которых равна n.
Например: ввод n = 13, вывод:
2 2 2 2 2 3
2 2 2 2 5
2 2 2 7
2 2 3 3 3
2 3 3 5
2 11
3 3 7
3 5 5
13
Вывод сортируется лексикографическим методом.
Я просто мог написать код для поиска простых чисел между 1-n:
n = int(input())
lst = []
for i in range(2, n + 1):
isPrime = True
for j in range(2, i - 1):
if i % j == 0:
isPrime = False
if isPrime:
lst.append(i)
print(lst)
на самом деле есть (строка 5), но вывод сортируется лексикографическим методом
У вас есть все числа, так что вам просто нужно узнать, как суммировать список? или просто как сложить числа внутри цикла?
нет, мне нужно найти все случаи простых чисел, сумма которых равна n
До сих пор не понятно, в чем ваш вопрос. Вы хотите, чтобы кто-то сделал вашу домашнюю работу за вас, то есть разработал для этого алгоритм? Какие подходы вы знаете, от каких уже отказались?
Ваш вопрос по-прежнему сбивает с толку и звучит так, как будто вы хотите, чтобы кто-то написал всю программу за вас (делал за вас домашнюю работу?), если это не так, пожалуйста, отредактируйте сообщение, чтобы уточнить ваш вопрос. Включите все ошибки, с которыми вы столкнулись.
к сожалению, я не знаю какого-либо конкретного алгоритма для решения этой проблемы.
Добро пожаловать в Stack Overflow. Пожалуйста, прочтите Как задавать вопросы и Как задавать домашние вопросы и отвечать на них?. Мы требуем, чтобы вопросы были конкретными и целенаправленными. Должно быть совершенно ясно, что «вычислить все возможные группы простых чисел, сумма которых равна N, и отобразить их» — это многоэтапный процесс. Вы несете ответственность за то, чтобы попытаться определить шаги и выяснить, где вы застряли.
Ответы 1
Вот мой взгляд на проблему.
solution = []
primes_up_to_n = [2, 3, 5, 7, 11, 13]
def get_sums(primes, n, path):
global solution # keep track of solutions found so far.
if n < min(primes):
return # no more solutions are possible at this point
for prime in primes:
if n == prime:
solution.append(path+[prime])
get_sums(primes, n-prime, path+[prime])
get_sums(primes_up_to_n , 13, [])
k = [sorted(x) for x in solution] # order the solutions
print([*map(list, {*map(tuple, k)})]) # remove the duplicates
Объяснение:
- мы проверяем, находится ли текущий n в списке простых чисел. Если это так, это означает, что
path + [n]является решением, поэтому мы добавляем его. - мы рекурсивно вызываем
get_sums, чтобы найти дальнейшие решения. Проблема с этим подходом заключается в том, что алгоритм, например, не различает[2, 2, 2, 2, 2, 3]и[2, 2, 2, 2, 3, 2]. Таким образом мы избавляемся от таких дубликатов в последних двух строках.
Код выводит:
[[2, 2, 2, 2, 2, 3],
[2, 2, 2, 7],
[2, 3, 3, 5],
[13],
[3, 3, 7],
[2, 2, 3, 3, 3],
[3, 5, 5],
[2, 2, 2, 2, 5],
[2, 11]]
Пожалуйста, прочтите Как ответить, а не просто пишите код по спецификации. Подобные вопросы не подходят для Stack Overflow, а код в ответах необходимо пояснять.
@Karl Knechtel Извините за это. Я думал, что человек попробовал, но в будущем я буду осторожнее. Для пояснений я отредактировал свой пост и надеюсь, что теперь он понятнее.
Привет и добро пожаловать в Stack Overflow. Неясно, в чем заключается ваш вопрос, не могли бы вы отредактировать вопрос и указать, с чем вам нужна помощь?