77 lines
3.2 KiB
Python
77 lines
3.2 KiB
Python
''' ****** Задание 20 из 20 *********
|
||
* Напомним, что взаимно простыми называются числа, которые не имеют общих делителей, кроме 1.
|
||
|
||
Напишите программу, которая:
|
||
|
||
получает список чисел, разделённых точкой с запятой и пробелом;
|
||
для каждого числа определяет, с какими другими числами оно взаимно просто;
|
||
выводит результат в порядке возрастания чисел без повторений;
|
||
если для числа не найдено ни одного взаимно простого числа — его не нужно выводить вовсе.
|
||
Формат ввода
|
||
Задана последовательность чисел записанных через точку с запятой (;) и пробел.
|
||
|
||
Формат вывода
|
||
Список чисел с указанием взаимно простых ему среди переданных.
|
||
Все числа должны быть выведены в порядке возрастания без повторений.
|
||
Строки следует отформатировать по правилу:
|
||
число - взаимно простое 1, взаимно простое 2, ...
|
||
Если для числа не было найдено ни одного взаимно простого, то и выводить его не требуется.
|
||
|
||
|
||
Подсказка
|
||
Рассмотрите все возможные пары чисел.
|
||
|
||
Если два числа a и b являются взаимно простыми, то по ключу a в список добавьте b и наоборот.
|
||
|
||
Пример 1
|
||
Ввод
|
||
|
||
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
|
||
'''
|
||
|
||
|
||
if __name__ == "__main__":
|
||
data = sorted(map(int, input().split('; ')))
|
||
result = dict.fromkeys(data)
|
||
for i in data:
|
||
for j in data:
|
||
a, b = i, j
|
||
while b:
|
||
a, b = b, a % b
|
||
if a == 1:
|
||
if result[i]:
|
||
result[i].add(j)
|
||
else:
|
||
result[i] = {j}
|
||
for number in result:
|
||
if result[number]:
|
||
print(f'{number} - {", ".join(map(str, sorted(result[number])))}')
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|