Liczby pierwsze

Zgodnie z definicją liczba pierwsza to taka, która spełnia następujący warunek:

  • ma tylko dwa dzielniki: jeden i samą siebie.

Zaimplementujmy w języku C++ algorytm pozwalający sprawdzić, czy podana liczba jest liczbą pierwszą.

Zacznijmy od utworzenia dwóch zmiennych: jednej typu całkowitego (int) o nazwie liczbaTest oraz drugiej typu bool, która będzie się nazywać czyPierwsza. Do liczbaTest zostanie zapisana liczba, którą użytkownik wpisał na klawiaturze, w celu sprawdzenia, czy jest ona liczbą pierwszą. Natomiast zmienna czyPierwsza będzie przyjmować wartość true lub false w zależności od tego, czy mamy do czynienia z liczbą pierwszą, czy też nie.

Ponieważ wspomnieliśmy o interakcji programu z użytkownikiem, napiszmy kod odpowiedzialny za możliwość wprowadzenia przez użytkownika własnych danych, czyli w tym przypadku liczby, która ma zostać poddana sprawdzeniu.

Linia 1. int liczbaTest średnik. Linia 2. bool czyPierwsza średnik. Linia 4. std dwukropek dwukropek cin zamknij nawias ostrokątny zamknij nawias ostrokątny liczbaTest średnik.

Następnym krokiem będzie napisanie pętli, w której będziemy sprawdzać liczby od 2 do liczby mniejszej o jeden od podanej. Ponieważ dzielnikami liczby pierwszej jest 1 i podana liczba, więc w przedziale 2, liczbaTest - 1 nie powinno być żadnego dzielnika podanej liczby. W przypadku wykrycia dzielnika całkowitego pętla zostanie przerwana instrukcją break, a zmienna logiczna czyPierwsza przyjmie wartość false, co będzie oznaczało, że podana przez użytkownika liczba nie jest liczbą pierwszą.

Linia 1. for otwórz nawias okrągły int i znak równości 2 średnik i otwórz nawias ostrokątny liczbaTest średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. if otwórz nawias okrągły liczbaTest procent i znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. czyPierwsza znak równości false średnik. Linia 4. break średnik. Linia 5. zamknij nawias klamrowy. Linia 6. zamknij nawias klamrowy.
Ważne!

Możemy zoptymalizować nasz algorytm i sprawdzanie, czy liczba jest dzielnikiem liczbaTest wykonywać w przedziale  2,liczbaTest. Pętlę for można wtedy przekształcić następująco: for(int i = 2; i*i  <= liczbaTest; i++). Zapis i*i <= liczbaTest wynika z podniesienia dwóch stron do kwadratu, aby pozbyć się pierwiastka. Dlaczego sprawdzanie wystarczy dokonać tylko do pierwiastka liczby? Przeanalizujmy przykłady liczb 18 oraz 16 i wypiszmy ich dzielniki:

18 4 , 24

Dzielniki 18 = { 1, 2, 3, |4.24|, 6, 9, 18}

16   =   4

Dzielniki 16 = { 1, 2, |4|, 8, 16}

Pomiędzy znakami || zapisano wartość bezwzględną pierwiastka liczby n.

Można zauważyć, że jeśli liczba n ma dzielniki większe od 1, to posiada ich tyle samo po obu stronach od n  . W przypadku liczb kwadratowych np. 16, 25, 36 itp. pierwiastek liczby będzie jej dzielnikiem.

Linia 1. for otwórz nawias okrągły int i znak równości 2 średnik i asterysk i otwórz nawias ostrokątny znak równości liczbaTest średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. if otwórz nawias okrągły liczbaTest procent i znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. czyPierwsza znak równości false średnik. Linia 4. break średnik. Linia 5. zamknij nawias klamrowy. Linia 6. zamknij nawias klamrowy.

Na koniec określamy, jaki komunikat ma się pojawić na standardowym wyjściu, w zależności od tego, jaka jest wartość zmiennej czyPierwsza.

Linia 1. if otwórz nawias okrągły czyPierwsza znak równości znak równości true zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. std dwukropek dwukropek cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Podana liczba jest liczbą pierwszą cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny std dwukropek dwukropek endl średnik. Linia 3. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 4. std dwukropek dwukropek cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Podana liczba nie jest liczbą pierwszą cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny std dwukropek dwukropek endl średnik. Linia 5. zamknij nawias klamrowy.
Ciekawostka

Instrukcję warunkową if(czyPierwsza == true) można zapisać również jako if(czyPierwsza).

Zobaczmy kod całego programu.

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int liczbaTest średnik. Linia 7. bool czyPierwsza znak równości true średnik. Linia 9. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Podaj liczbę przecinek którą chcesz poddać sprawdzeniu dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 10. cin zamknij nawias ostrokątny zamknij nawias ostrokątny liczbaTest średnik. Linia 12. for otwórz nawias okrągły int i znak równości 2 średnik i otwórz nawias ostrokątny liczbaTest średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły liczbaTest procent i znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. czyPierwsza znak równości false średnik. Linia 15. break średnik. Linia 16. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 19. if otwórz nawias okrągły czyPierwsza znak równości znak równości true zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Podana liczba jest liczbą pierwszą cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny std średnik. Linia 21. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 22. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Podana liczba nie jest liczbą pierwszą cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny std średnik. Linia 23. zamknij nawias klamrowy. Linia 25. return 0 średnik. Linia 26. zamknij nawias klamrowy.

Warto zauważyć, że w tej implementacji algorytmu wychodzimy z założenia, że podana liczba jest liczbą pierwszą, ponieważ przy deklaracji zmiennej logicznej czyPierwsza nadajemy jej wartość true. Po wykonaniu pętli for, jeżeli wartość czyPierwsza nie zostanie zmieniona, jej wartość nadal będzie wynosić true, a my uzyskamy pewność, że mamy do czynienia z liczbą pierwszą.

Liczby doskonałe

Zacznijmy od przypomnienia warunku, jaki musi spełniać liczba doskonała:

  • Suma dzielników mniejszych od sprawdzanej liczby musi być równa tej liczbie.

Przykładami liczb doskonałych są:

  • 6, ponieważ:

1+2+3=6

gdzie 1, 2 i 3 to dzielniki właściwedzielniki właściwedzielniki właściwe liczby 6.

  • 28, ponieważ:

1+2+3+4+7+14=28

gdzie 1, 2, 3, 4, 7, 14 to dzielniki właściwe liczby 28.

Można zauważyć, że nasz algorytm będzie polegał na znalezieniu dzielników podanej liczby, zsumowaniu ich i sprawdzeniu, czy wynik jest równy sprawdzanej liczbie. Przeanalizujmy kod programu, który stanowi rozwiązanie tego problemu:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int liczba średnik. Linia 7. int sumaDzielnikow znak równości 0 średnik. Linia 9. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Podaj liczbę do sprawdzenia dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny std średnik. Linia 10. cin zamknij nawias ostrokątny zamknij nawias ostrokątny liczba średnik. Linia 12. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny liczba średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły liczba procent i znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. sumaDzielnikow znak równości sumaDzielnikow plus i średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy. Linia 18. if otwórz nawias okrągły sumaDzielnikow znak równości znak równości liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Dana liczba jest liczbą doskonałą cudzysłów średnik. Linia 20. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 21. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Dana liczba nie jest liczbą doskonałą cudzysłów średnik. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy.

W pętli for sprawdzamy, czy kolejne liczby (zaczynając od 1) są dzielnikami zmiennej liczbaTest. Jeżeli znajdziemy taki dzielnik, dodajemy go do zmiennej sumaDzielnikow. Następnie porównujemy wartość zmiennej sumaDzielnikow z podaną do sprawdzenia liczbą. Jeżeli są one równe, to jest to liczba doskonała.

Liczba doskonała – optymalizacja algorytmu

Zastanówmy się, czy można zoptymalizować przedstawiony wyżej algorytm. Pierwszą rzeczą, którą możemy zrobić, jest rozpoczęcie przetwarzanie pętli od liczby 2, ponieważ każda liczba jest podzielna przez 1. Unikniemy dzięki temu jednej, niepotrzebnej iteracji.

Możemy także dodać warunek wewnątrz pętli. Pozwoli to sprawdzić, czy aktualna wartość zmiennej sumaDzielnikow nie jest większa od badanej liczby. W ten sposób uda się uniknąć wykonywania wielu niepotrzebnych cykli pętli.

Niżej przedstawiamy kod programu po wprowadzeniu zmian optymalizacyjnych.

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int liczba średnik. Linia 7. int sumaDzielnikow znak równości 1 średnik. Linia 9. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Podaj liczbę do sprawdzenia dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny std średnik. Linia 10. cin zamknij nawias ostrokątny zamknij nawias ostrokątny liczba średnik. Linia 12. for otwórz nawias okrągły int i znak równości 2 średnik i otwórz nawias ostrokątny liczba średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły liczba procent i znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. sumaDzielnikow znak równości sumaDzielnikow plus i średnik. Linia 16. if otwórz nawias okrągły sumaDzielnikow zamknij nawias ostrokątny liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. break średnik. Linia 18. zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 20. zamknij nawias klamrowy. Linia 22. if otwórz nawias okrągły sumaDzielnikow znak równości znak równości liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Dana liczba jest liczba doskonałą cudzysłów średnik. Linia 24. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 25. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Dana liczba nie jest liczba doskonałą cudzysłów średnik. Linia 26. zamknij nawias klamrowy. Linia 27. zamknij nawias klamrowy.

Liczby zaprzyjaźnione

Liczby zaprzyjaźnione to takie, których suma dzielników właściwych pierwszej liczby jest równa wartości drugiej liczby, a suma dzielników właściwych drugiej liczby jest równa wartości pierwszej liczby.

Przykładem pary takich liczb są: 220 i 284.

Dzielniki właściwe liczby 220 to: 1+2+4+5+10+11+20++22+44+55+110=284. Natomiast dzielniki właściwe liczby 284 to: 1+2+4+71+142=220.

Przeanalizujmy implementację algorytmu, która pozwoli sprawdzić, czy podane przez użytkownika dwie liczby są zaprzyjaźnione.

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int liczba1 przecinek liczba2 średnik. Linia 7. int l1Suma znak równości 0 średnik. Linia 8. int l2Suma znak równości 0 średnik. Linia 10. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Podaj pierwszą liczbę do sprawdzenia dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny std średnik. Linia 11. cin zamknij nawias ostrokątny zamknij nawias ostrokątny liczba1 średnik. Linia 12. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Podaj drugą liczbę do sprawdzenia dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny std średnik. Linia 13. cin zamknij nawias ostrokątny zamknij nawias ostrokątny liczba2 średnik. Linia 15. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny liczba1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. if otwórz nawias okrągły liczba1 procent i znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. l1Suma plus znak równości i średnik. Linia 18. zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 21. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny liczba2 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. if otwórz nawias okrągły liczba2 procent i znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. l2Suma plus znak równości i średnik. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy. Linia 27. if otwórz nawias okrągły liczba1 znak równości znak równości l2Suma ampersant ampersant liczba2 znak równości znak równości l1Suma zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów To są liczby zaprzyjaźnione cudzysłów średnik. Linia 29. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 30. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów To nie są liczby zaprzyjaźnione cudzysłów średnik. Linia 31. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy.

Na początku programu deklarujemy zmienne liczba1liczba2. To w nich zapiszemy liczby, które użytkownik podał do sprawdzenia. Kolejne zmienne to l1Suma oraz l2Suma. Będą one odpowiadały kolejno sumie dzielników właściwych liczby pierwszej i sumie dzielników właściwych liczby drugiej.

Następnie w pętlach for sprawdzamy kolejne dzielniki liczb i sumujemy je. W końcowej części programu porównujemy wartość pierwszej liczby z sumą dzielników liczby drugiej i wartość liczby drugiej z sumą dzielników liczby pierwszej, a następnie wypisujemy odpowiedni komunikat.

Słownik

dzielniki właściwe
dzielniki właściwe

dzielniki liczby mniejsze od niej samej