Dvě čísla \(a\) a \(b\) jsou nesoudělná, pokud je jejich největší společný dělitel (NSD) roven 1. NSD je největší kladné číslo, které dělí obě daná čísla \(a\) a \(b\). Například čísla 7 a 9 jsou nesoudělná, protože jejich NSD je 1.

Máš k dispozici dva seznamy list1 a list2. Tvým úkolem je vytvořit nový seznam coprimes, který bude obsahovat všechny nesoudělné dvojice z list1 a list2.

Nejdřív ale musíš napsat funkci pro výpočet NSD podle následujícího algoritmu:

zkontroluj, zda \(b = 0\)
- pokud ano, vrať \(a\) jako NSD čísel \(a\) a \(b\)
- pokud ne, přejdi na krok 2
proveď substituci \(a \leftarrow b\) a \(b \leftarrow a \% b\)
vrať se na krok 1

Co je generátor a jak ho vytvořit?

Create Your Free Account