Sprawdzenie czy zbiórdzielników pierwszych liczby a jest podzbiorem dzielnikow pierwszych liczby b

Question

Mam dwie liczby całkowite a i b gdzie a <= b, i ma stwierdzić czy zbiór dzielników pierwszych liczby a jest podzbiorem dzielników pierwszych liczby b.

I mam taką odpowiedź ale nie do końca ją rozumiem:

Jeśli zbiór dzielników pierwszych a > 1 zawiera się w zbiorze dzielników pierwszych b, to zbiór dzielników pierwszych nwd(a, b) zawiera w sobie co najmniej po jednym ich dzielniku. Następnie, możemy dzielić a przez nwd(a, b) dopóty, dopóki nwd(a, b) != 1.

Dlaczego tak jest? Pomoże mi ktoś to zrozumieć?

Comments

To jest nadal ALGORYTM EUKLIDESA, pomyśl pomyśl!
Rozpisz sobie to na kartce. Zaraz Ci pokażę

Answer 1

To jest nadal ALGORYTM EUKLIDESA, pomyśl pomyśl! 
Rozpisz sobie to na kartce.

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.

1 2 3 4 5 6

x = 1960 x-zbiór: 2  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.

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

 

Comments

Algorytm jest w istocie taki :
 

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).

---

Dobra chyba rozumiem:

    int a = 4;              // mniejsza liczba i mniejszy zbior
    int b = 10;             // wieksza liczba i wiekszy zbior
    while (nwd(a, b) != 1)  // dopoki a_zbior nie jest pusty lub a i b nie beda mialy innego wspolego dzielnika oprocz 1
        a /= nwd(a, b)      // od zbioru a odejmujemy czesc wspolna a i b
    wynik = (a === 1);      // jesli a == 1 to znaczy ze a_zbior jest pusty i a_zbior jest caly w b_zbiorze 
                            // w przeciwnym wypadku a nie jest pusty i nie zawiera sie caly w b_zbiorze

"Jak sprawdzić czy część_wspólna_a_b-zbiór jest pusty?
Odp: Jeżeli jest pusty, to NWD(a, b)" jest równe 1 i a jest równe 1

Chyba o to Ci tutaj chodziło ?

Dzięki wielkie za pomoc ! 

EDIT: W warunku powinno być chyba // dopóki a i b mają wspólny dzielnik pierwszy