„Zbiór pierwszych” – omówienie (Algorytm Euklidesa)

O co chodzi w zadaniu?

Mamy z zestawów danych. Przy każdym zestawie na wejście dostajemy dwie liczby całkowite a oraz b. Musimy odpowiedzieć na następujące pytanie: „czy zbiór dzielników pierwszych liczby a jest podzbiorem dzielników pierwszych liczby b”.

Jak się zabrać za zadanie?

Pierwszym skojarzeniem po przeczytaniu pary słów: „liczby pierwsze” jest najprawdopodobniej sito Eratostenesa. Zauważ jednak, że każda z liczba a oraz mieści się w przedziale od 1 do 10^9. Oznacza to, że po użyciu sita, które ma złożoność O(n log log n) nasze rozwiązanie nie będzie w stanie przejść testów na sprawdzarce, gdyż ma nieefektywną złożoność. Jak się zapewne domyślasz, istnieje rozwiązanie, które nie będzie wymagać od nas użycia sita. Wyobraźmy sobie zbiór, który zawiera dzielniki pierwsze danej liczby x. Będzie on nieco inny, niż ten o którym mowa w zadaniu, gdyż dany dzielnik pierwszy d będzie w nim występować tyle razy, ile razy możemy dzielić daną liczbę x przez dzielnik d, np.

x = 1960
x-zbiór:
2  2  2
brak
5
7  7

W ten sposób będziemy reprezentować liczby a oraz b. W jaki sposób możemy wykorzystać taką reprezentację? Rozważmy na następnym przykładzie:

a-zbiór:
2  2  2  2
3
5  5  5
7  7  7  7  7
brak

b-zbiór:
2  2
brak
5
7  7
11  11  11

Z tych zbiorów wyciągnijmy część wspólną:

część_wspólna_a_b-zbiór:
2  2
brak
5
7  7

Zauważmy, że jeżeli „zbiór dzielników pierwszych liczby a jest podzbiorem dzielników pierwszych liczby b”, to część wspólna zbiorów a-zbiór oraz b-zbiór będzie zawierać wszystkie dzielniki liczby a. W naszym przypadku część wspólna nie zawiera liczby 3 – dzielnika pierwszego liczby a, z czego wynika że zbiór dzielników pierwszych liczby a NIE jest podzbiorem dzielników pierwszych liczby b. Skąd zatem możemy wiedzieć, czy część wspólna zawiera wszystkie dzielniki liczby a?  Jeżeli udałoby się nam usunąć ze zbioru a-zbiór wszystkie elementy o wartości występującej w części wspólnej, będziemy w stanie stwierdzić czy spełniony został warunek, o którym mowa w zadaniu. W przypadku gdy a-zbiór jest pusty, warunek został spełniony, w przeciwnym wypadku nie został spełniony.

Algorytm na przykładzie

Mamy już ogólny zarys tego, jak będziemy postępować. Wprowadźmy następującą operację usuwania: ze zbioru X usuń elementy ze zbioru Y, np.

X = {2, 2, 2, 2, 2, 5, 7, 7, 11}
Y = {2, 2, 7}

X po 1. usunięciu:
X = {2, 2, 2, 5, 7, 11}

X po 2. usunięciu:
X = {2, 5, 11}

Ustalmy, że nie możemy wykonać operacji usuwania, jeżeli brakuje elementów, tzn. usunąć ze zbioru X elementów: 2, 2, 7, gdyż te nie występują w odpowiedniej liczbie: elementy o wartości 2 musiałyby wystąpić w zbiorze X co najmniej 2 razy, element o wartości 7 musiałby wystąpić w zbiorze X co najmniej raz.

Powróćmy teraz do naszego pierwszego przykładu:

a-zbiór:
2  2  2  2
3
5  5  5
7  7  7  7  7
brak

b-zbiór:
2  2
brak
5
7  7
11  11  11

część_wspólna_a_b-zbiór:
2  2
brak
5
7  7

Ze zbioru a-zbiór usuwajmy część wspólną, dopóki jest to możliwe (zgodnie z tym, co zostało zapisane powyżej). Przed usunięciem:

a-zbiór:
2  2  2  2
3
5  5  5
7  7  7  7  7
brak

Po 1. usunięciu:

a-zbiór:
2  2
3
5  5
7  7  7
brak

Po 2. usunięciu:

a-zbiór:
brak
3
5
7
brak

W tej chwili nie możemy już wykonywać operacji usuwania. Stwórzmy więc nową część wspólną: z obecnego zbioru a-zbiór oraz ze zbioru b-zbiór:

część_wspólna_a_b-zbiór:
brak
brak
5
7

Ze zbioru a-zbiór usuńmy teraz nową część wspólną:

a-zbiór:
brak
3
brak
brak
brak

Zbiór nie jest pusty, a więc warunek z zadania nie został spełniony. Algorytm, którego celem jest usunięcie ze zbioru a-zbiór wszystkich elementów, których wartości występują również w początkowej części wspólnej, wygląda następująco:

utwórz część_wspólna_a_b-zbiór
dopóki część_wspólna_a_b-zbiór nie jest pusty, wykonuj:
dopóki od a-zbiór można odjąć część_wspólna_a_b-zbiór, wykonuj:
                    od a-zbiór odejmij część_wspólna_a_b-zbiór
utwórz część_wspólna_a_b-zbiór
jeżeli a-zbiór jest pusty
napisz TAK
w przeciwnym wypadku
napisz NIE

Implementacja

Każdą liczbę naturalną dodatnią da się przedstawić, jako iloczyn kolejnych liczb pierwszych podniesionych do odpowiednich potęg, np.

1960 = 2^3 * 3^0 * 5^1 * 7^2

Takie zapisanie liczby, odzwierciedla bardzo dobrze zbiór, który omawialiśmy. Potęga przy liczbie pierwszej informuje nas, ile elementów o danej wartości występuje w zbiorze. Co do implementacji, należy zadać następujące pytania:

  1. Jak przedstawić a-zbiór, b-zbiór?
    Odp: a-zbiór, to po prostu a, zaś b-zbiór to b.
  2. Jak przedstawić część wspólną?
    Odp: Cześć wspólna zbiorów to NWD(a, b).
  3. Jak sprawdzić czy część_wspólna_a_b-zbiór jest pusty?
    Odp: Jeżeli jest pusty, to NWD(a, b).
  4. Jak sprawdzić czy od a-zbiór można odjąć część_wspólna_a_b-zbiór?
    Odp: Jeżeli NWD(a, b) liczysz na bieżąco (przy sprawdzaniu jest używana funkcja wyliczająca NWD), to zawsze możesz to zrobić, gdyż wyliczone w tej chwili NWD musi być dzielnikiem liczby a.
  5. Jak od a-zbiór odjąć część_wspólna_a_b-zbiór?
    Odp: a = a/NWD(a,b).

UWAGA!
Przy liczeniu na bieżąco NWD(a, b), czyli nieprzechowywaniu go w żadnej zmiennej, Twój algorytm powinien skrócić się do tej postaci:

dopóki teraz_wyliczona_część_wspólna_a_b-zbiór nie jest pusta, wykonuj:
od a-zbiór odejmij teraz_wyliczona_część_wspólna_a_b-zbiór
jeżeli a-zbiór jest pusty
napisz TAK
w przeciwnym wypadku
napisz NIE

Zakodowanie zadania pozostawiam w Waszej gestii 🙂

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *

*