Strona główna » Algorytmy » Teoria Liczb » Liczby Względnie pierwsze
a1....
 

Liczby Względnie pierwsze

https://mattomatti.com/a76

Definicja

Liczby Względnie pierwsze są to takie liczby całkowite, których największym wspólnym dzielnikiem jest 1. Wyróżnia się też Liczby parami względnie pierwsze. W tym przypadku są to liczby całkowite, gdzie każda para liczb jest Względnie pierwsza.

Powyższą definicję najłatwiej zapisać dla liczb , że , gdzie funkcja NWD oznacza największy wspólny dzielnik.

Przykłady

Liczby 4 i 9 nie są liczbami pierwszymi, ale są względnie pierwsze, ponieważ NWD(4, 9) = 1. Innym przykładem takich liczb jest 11 i 15. Tutaj też NWD(11, 15) = 1. Dla pary liczb liczby są zawsze parami względnie pierwszymi co jednak nie jest zawsze prawdą dla większej ilości liczb, ponieważ {6, 7, 8} są względnie pierwsze, bo NWD(6, 7, 8) = 1, ale NWD(6, 8) = 2. Przykładem trójki liczb parami względnie pierwszych są liczby {1, 2, 5}. Warto zauważyć, że para liczb jest zawsze względnie pierwsza jeśli jedna z liczb wynosi 1.

Dwie liczby

Najprostszym przypadkiem jaki można wyodrębnić to sprawdzanie dwóch liczb czy są względnie pierwsze. Najprostszą metodą, która pozwala tego dokonać jest Algorytm Euklidesa:

  1. int nwd(int a,int b){
  2.   return (a==0) ? b : nwd(b%a,a);
  3. }

Posiadając funkcję nwd() funkcja sprawdzająca czy para liczb jest względnie pierwsza musi sprawdzić czy NWD wyniosło 1:

  1. bool czyWzgledniePierwsze2 (int a, int b) {
  2.   return (nwd(a, b) == 1);
  3. }

Testowanie funkcji

Powyższą funkcję można przetestować przy pomocy poniższej funkcji main():

  1. int main () {
  2.   int a, b;
  3.   cin >> a >> b;
  4.   cout << (czyWzgledniePierwsze2(a, b) ? "TAK" : "NIE") << endl;
  5.   system("pause");
  6.   return 0;
  7. }

Dowolna ilość liczb

Względnie pierwsze

Przypadek kiedy jest do sprawdzenia n liczb wymaga pewnych dopasowań dotychczasowych funkcji. Po pierwsze należy pamiętać, że NWD n liczb wyniesie dokładnie 1 wtedy i tylko wtedy, gdy nie istnieje dzielnik, który podzieli wszystkie n liczb. Po drugie nie ma potrzeby szukania dzielnika powyżej połowy najmniejszej z n liczb. Wymienione zasady trzeba zastosować w przedstawionej kolejności w algorytmie:

  1. bool czyWzgledniePierwsze (int* l, int n) {
  2.   int min = l[0];
  3.   for(int i = 1; i < n; i++)
  4.     if(l[i] < min)
  5.       min = l[i];
  6.   for(int i = 2; i <= min/2; i++){
  7.     bool podzielne = true;
  8.     for(int j = 0; j < n; j++)
  9.       podzielne = podzielne && (l[j] % i == 0);
  10.     if(podzielne)
  11.       return false;
  12.   }
  13.   return true;
  14. }

(1.) Funkcja czyWzgledniePierwsze() przyjmuje dwa argumenty: l - listę liczb oraz n - ile liczb ma lista l. (2. - 5.) Znalezienie na liście najmniejszej wartości i zapisanie do zmiennej min. (6.) Dla każdego możliwego dzielnika: (7.) zakładamy, że wszystkie liczby na liście są przez niego podzielne. (8.) Dla każdej liczby na liście: (9.) sprawdzamy jej podzielność przez aktualnie sprawdzany dzielnik i. Tutaj wykorzystana została cecha koniunkcji. Jeśli którakolwiek z liczb nie jest podzielna przez i to podzielne do końca sprawdzania listy będzie miało już wartość fałsz. Jednak jeśli (10.) wszystkie liczby okażą się podzielne przez i to (11.) należy zwrócić fałsz. Jeśli pętla zostanie zakończona i żadne dzielnik nie zostanie znaleziony to (13.) można zwrócić prawda.

Parami względnie pierwsze

Podczas sprawdzania czy liczby są parami względnie pierwsze to należy pamiętać, że jeśli a i b oraz b i c są względnie pierwsze to z tego nie wynika, że a i c też są. W przypadku sprawdzania tej cechy zbioru liczb należy sprawdzić wszystkie pary liczb. Do implementacji algorytmu można wykorzystać pętle z Sortowania bąbelkowego:

  1. bool czyParamiWzgledniePierwsze (int* l, int n) {
  2.   for(int i = 0; i + 1 < n; i++)
  3.     for(int j = i + 1; j < n; j++)
  4.       if(!czyWzgledniePierwsze2(l[i], l[j]))
  5.         return false;
  6.   return true;
  7. }

(4.) Jeśli aktualnie przeglądana para liczb nie jest względnie pierwsza to można (5.) zwrócić fałsz. Jednak dopiero po sprawdzeniu wszystkich par (6.) można stwierdzić, że liczby są parami względnie pierwsze.

Testowanie funkcji

Poniższa funkcja main() pozwoli wczytać n liczb i sprawdzić czy liczby są względnie pierwsze oraz czy są parami względnie pierwsze:

  1. int main () {
  2.   int n;
  3.   cout << "Pod ile liczb ma lista:";
  4.   cin >> n;
  5.   int* l = new int[n];
  6.   for(int i = 0; i < n; i++)
  7.     cin >> l[i];
  8.   cout << "liczby " << (czyWzgledniePierwsze(l, n) ? "" : "nie ");
  9.   cout << "sa " << (czyParamiWzgledniePierwsze(l, n) ? "parami " : "");
  10.   cout << "wzglednie pierwsze" << endl;
  11.   system("pause");
  12.   return 0;
  13. }

Zadania

  1. Napisz funkcję generujWzgledniePierwsze(), która dla podanej wartości n wygeneruje listę n liczb względnie pierwszych.
  2. Polecenie jak w poprzednim ćwiczeniu. Tym razem jednak nie wolno umieścić na liście żadnej liczby pierwszej.