Напомним, что взаимно простыми называются числа, которые не имеют общих делителей кроме 1. Напишите программу, которая для каждого переданного числа находит список его взаимно простых.
Формат ввода
Задана последовательность чисел записанных через точку с запятой (;) и пробел.
Формат вывода:
Список чисел с указанием взаимно простых ему среди переданных.
Все числа должны быть выведены в порядке возрастания без повторений.
Строки следует отформатировать по правилу:
число – взаимно простое 1, взаимно простое 2, …
Если для числа не было найдено ни одного взаимно простого, то и выводить его не требуется.
Пример
Ввод
2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20Вывод
2 - 3, 5, 7, 9, 11, 13, 15, 17, 19
3 - 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20
4 - 3, 5, 7, 9, 11, 13, 15, 17, 19
5 - 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19
6 - 5, 7, 11, 13, 17, 19
7 - 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20
8 - 3, 5, 7, 9, 11, 13, 15, 17, 19
9 - 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20
10 - 3, 7, 9, 11, 13, 17, 19
11 - 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18, 19, 20
12 - 5, 7, 11, 13, 17, 19
13 - 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20
14 - 3, 5, 9, 11, 13, 15, 17, 19
15 - 2, 4, 7, 8, 11, 13, 14, 16, 17, 19
16 - 3, 5, 7, 9, 11, 13, 15, 17, 19
17 - 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20
18 - 5, 7, 11, 13, 17, 19
19 - 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 20
20 - 3, 7, 9, 11, 13, 17, 19Ввод
7; 2; 2; 12; 14; 7; 2; 49Вывод
2 - 7, 49
7 - 2, 12
12 - 7, 49
49 - 2, 12Решение
Описание задачи часто пугает учащихся, но на самом деле задача имеет довольно просто решение.
Считываем строку и делим ее на числа используя в качестве разделителя точку с запятой и пробел (‘; ‘).
Преобразуем получившиеся строки в целые числа, предварительно избавившись от дубликатов с помощью преобразования в множество.
Организуем вложенный цикл перебирая взаимные пары чисел и проверяя их НОД. Если НОД оказался равным единице, то добавляем второе число в список.
По окончании внутреннего цикла проверяем не пуст ли список, и если не пуст, выводим, отформатированный список.
Посмотреть код
Решение
items = set(input().split('; '))
numbers = []
for item in items:
numbers.append(int(item))
numbers.sort()
for num1 in numbers:
mutually = []
for num2 in numbers:
if num1 != num2:
a, b = num1, num2
while b != 0:
a, b = b, a % b
if a == 1:
mutually.append(str(num2))
if mutually:
print(num1, '-', ", ".join(mutually))
Добрый день!
Ваше решение очень элегантное, мое более топорное и явно с излишками, но тем не менее.
Подскажите, пожалуйста: для первого примера мой вариант проходит, а вот со вторым выдает ошибку и вылетает код на числе 49 при принте.
С чем это связано?
number_list = []
subsequence = list(set(input().split(‘; ‘)))
itog = {}
number_list = sorted(set([int(number) for number in subsequence]))
for number in sorted(number_list):
for i in range(len(number_list)):
current_number = int(number_list[i])
number_digit = int(number)
is_simple = True
if current_number == number_digit:
continue
if number_digit > current_number:
(current_number, number_digit) = (number_digit, current_number)
while current_number != 1 and number_digit != 1:
if current_number % number_digit == 0:
is_simple = False
break
else:
current_number = current_number % number_digit
(current_number, number_digit) = (number_digit, current_number)
if is_simple is True:
current_number = int(number_list[i])
itog[number] = itog.get(number, []) + [current_number]
for number in number_list:
print(f'{number} – {str(itog[number])[1:-1]}’)
Стоит оформлять код, как код. В комментариях есть кнопка, которая сохраняет форматирование.
Ваша программа ломается, на последнем этапе вывода чисел, когда встречает число, у которого нет взаимно простых среди чисел, представленных в списке.
Такое число не попадает в словарь и соотвественно строка, которая должна печатать ответ получает ответ, что в словаре нет элемента с таким индексом.
Есть два варианта решения проблемы.
Первый состоит в том, чтобы проверять перед выводом есть ли такое число в словаре, второй в том, чтобы проходить циклом по отсортированным ключам словаря.