Liczby pierwsze

Na początek przyjrzyjmy się grupie liczb nazywanych pierwszymi. Należą do nich np.:

  • 2,

  • 3,

  • 5,

  • 7,

  • 11,

  • 13,

  • 17.

Na pierwszy rzut oka trudno zauważyć jakąkolwiek właściwość, która byłaby wspólna dla wszystkich wymienionych wyżej liczb. Łączy je jednak pewna zależność dotycząca ich dzielnikówdzielnikdzielników.

Przypomnijmy więc – dana liczba jest liczbą pierwszą, jeśli spełnia dwa warunki:

  • jest liczbą naturalną większą od 1,

  • posiada tylko dwa dzielniki: 1 oraz samą siebie.

Problem 1

Spróbujmy napisać algorytm w postaci pseudokodu, który sprawdzi, czy dana liczba jest liczbą pierwszą.

Specyfikacja:

Dane:

  • liczba – liczba do sprawdzenia; liczba naturalna

Wynik:

Program wypisuje komunikat Liczba jest liczbą pierwszą lub Liczba nie jest liczbą pierwszą.

Linia 1. liczba ← wprowadź liczbę naturalną. Linia 2. czyPierwsza ← prawda. Linia 4. jeżeli liczba otwórz nawias ostrokątny znak równości 1 dwukropek. Linia 5. czyPierwsza ← fałsz. Linia 6. w przeciwnym razie dwukropek. Linia 7. i ← 2. Linia 8. dopóki i asterysk i otwórz nawias ostrokątny znak równości liczba dwukropek. Linia 9. jeżeli liczba mod i znak równości 0 dwukropek. Linia 10. czyPierwsza ← fałsz. Linia 11. przerwij pętlę. Linia 12. i ← i plus 1. Linia 14. jeżeli czyPierwsza znak równości prawda dwukropek. Linia 15. wypisz cudzysłów Liczba jest liczbą pierwszą cudzysłów. Linia 16. w przeciwnym razie dwukropek. Linia 17. wypisz cudzysłów Liczba nie jest liczbą pierwszą cudzysłów.

Zaczynamy od wprowadzenia liczby, która ma zostać sprawdzona, i zapisania jej w zmiennej liczba. Następnie deklarujemy zmienną logiczną czyPierwsza, której wartość będzie wskazywać, czy dana liczba spełnia warunki liczby pierwszej, czy też nie.

Kolejnym krokiem jest sprawdzenie w instrukcji warunkowej, czy wprowadzona liczba jest mniejsza lub równa 1. Jeśli ten warunek jest spełniony, dana liczba na pewno nie będzie liczbą pierwszą. Dlatego zmiennej logicznej czyPierwsza zostaje przypisana wartość fałsz.

W przeciwnym przypadku następuje sprawdzenie dzielników danej liczby z przedziału 2 , liczba . Jeżeli w zadanym przedziale zostanie znaleziony dzielnik, to liczba ta nie jest liczbą pierwszą. Sprawdzenie odbywa się w instrukcji warunkowej wewnątrz pętli. Wyrażenie mod oznacza operację modulo (w wielu językach programowania oznaczana symbolem %), czyli zwraca resztę z dzielenia liczby przez i.

Liczby doskonałe

Kolejną ciekawą grupą liczb są liczby doskonałe. Wyróżniająca je właściwość również dotyczy dzielników.

Aby daną liczbę naturalną można było nazwać doskonałą, suma jej dzielników właściwychdzielniki właściwedzielników właściwych musi być równa tej liczbie. Przykładami takich liczb są:

  • 6,

  • 28,

  • 496,

  • 8128.

Przyjrzyjmy się zatem dokładnie liczbie 6:

  • dzielniki właściwe: 1, 2, 3.

  • suma dzielników właściwych: 1 + 2 + 3 = 6.

  • Czy jest to liczba doskonała? TAK

Podobnie sprawdzimy liczbę 28:

  • dzielniki właściwe: 1, 2, 4, 7, 14.

  • suma dzielników właściwych: 1 + 2 + 4 + 7 + 14 = 28.

  • Czy jest to liczba doskonała? TAK

Problem 2

Napiszmy teraz algorytm w postaci pseudokodu, który sprawdzi, czy dana liczba jest liczbą doskonałą.

Specyfikacja:

Dane:

  • liczba – liczba do sprawdzenia; liczba naturalna

Wynik:

Program wypisuje komunikat Liczba jest liczbą doskonałą lub Liczba nie jest liczbą doskonałą.

Zapisany za pomocą pseudokodu algorytm sprawdzający, czy dana liczba jest liczbą doskonałą, będzie wyglądał następująco:

Linia 1. liczba ← wprowadź liczbę naturalną. Linia 2. sumaDzielników ← 0. Linia 4. dla i znak równości 1 przecinek 2 przecinek 3 przecinek kropka kropka kropka przecinek liczba minus 1 wykonuj dwukropek. Linia 5. jeżeli liczba mod i znak równości 0 dwukropek. Linia 6. sumaDzielników ← sumaDzielników plus i. Linia 8. jeżeli sumaDzielników znak równości liczba wykonaj dwukropek. Linia 9. wypisz cudzysłów Liczba jest liczbą doskonałą cudzysłów. Linia 10. w przeciwnym razie dwukropek. Linia 11. wypisz cudzysłów Liczba nie jest liczbą doskonałą cudzysłów.

Pierwszym krokiem jest wprowadzenie liczby, którą chcemy sprawdzić, i zapisanie jej wartości w zmiennej liczba. Następnie zostaje zadeklarowana zmienna sumaDzielników. Zmienna, jak wskazuje jej nazwa, będzie służyła do sumowania dzielników właściwych zadanej liczby.

Następnie zostaje zadeklarowana pętla, która iteruje po liczbach z przedziału 1 , liczba 1 , sprawdzając, czy dana wartość i jest dzielnikiem sprawdzanej liczby. Jeżeli tak, to następuje modyfikacja wartości zmiennej sumaDzielników. Wartość sumaDzielników zostaje zwiększona o wykryty dzielnik.

Ostatnim krokiem jest sprawdzenie, czy sumaDzielników jest równa sprawdzanej liczbie. Jeśli tak, oznacza to, że liczba ta jest liczbą doskonałą.

Liczby bliźniacze

Inną interesującą grupą są liczby bliźniacze. Są to pary liczb pierwszych, których różnica jest równa 2. Przykładami takich par będą:

  • 3 i 5,

  • 5 i 7,

  • 11 i 13,

  • 17 i 19,

  • 857 i 859.

Problem 3

Napiszmy algorytm w postaci pseudokodu, który sprawdzi, czy dane dwie liczby liczba1 oraz liczba2 są liczbami bliźniaczymi.

Specyfikacja:

Dane:

  • liczba1 – liczba do sprawdzenia; liczba naturalna

  • liczba2 – liczba do sprawdzenia; liczba naturalna

Wynik:

Program wypisuje komunikat Liczby są parą liczb bliźniaczych lub Liczby nie są parą liczb bliźniaczych.

Oto zapisany za pomocą pseudokodu algorytm sprawdzający, czy dwie zadane liczby są liczbami bliźniaczymi:

Linia 1. funkcja czyPierwsza otwórz nawias okrągły liczba zamknij nawias okrągły dwukropek. Linia 2. jeżeli liczba otwórz nawias ostrokątny znak równości 1 dwukropek. Linia 3. zwróć fałsz. Linia 4. w przeciwnym razie dwukropek. Linia 5. i ← 2. Linia 6. dopóki i asterysk i otwórz nawias ostrokątny znak równości liczba dwukropek. Linia 7. jeżeli liczba mod i znak równości 0 dwukropek. Linia 8. zwróć fałsz. Linia 9. i ← i plus 1. Linia 10. zwróć prawda. Linia 12. funkcja wartośćBezwzględna otwórz nawias okrągły liczba zamknij nawias okrągły dwukropek. Linia 13. jeżeli liczba otwórz nawias ostrokątny 0 dwukropek. Linia 14. zwróć minus liczba. Linia 15. w przeciwnym razie dwukropek. Linia 16. zwróć liczba. Linia 18. liczba1 ← wprowadź liczbę. Linia 19. liczba2 ← wprowadź liczbę. Linia 21. jeżeli wartośćBezwzględna otwórz nawias okrągły liczba1 minus liczba2 zamknij nawias okrągły znak równości 2 dwukropek. Linia 22. jeżeli czyPierwsza otwórz nawias okrągły liczba1 zamknij nawias okrągły znak równości prawda dwukropek. Linia 23. jeżeli czyPierwsza otwórz nawias okrągły liczba2 zamknij nawias okrągły znak równości prawda dwukropek. Linia 24. wypisz cudzysłów Liczby są parą liczb bliźniaczych cudzysłów. Linia 25. w przeciwnym razie dwukropek. Linia 26. wypisz cudzysłów Liczby nie są parą liczb bliźniaczych cudzysłów. Linia 27. w przeciwnym razie dwukropek. Linia 28. wypisz cudzysłów Liczby nie są parą liczb bliźniaczych cudzysłów. Linia 29. w przeciwnym razie dwukropek. Linia 30. wypisz cudzysłów Liczby nie są parą liczb bliźniaczych cudzysłów.

Funkcja czyPierwsza() sprawdza, czy dana liczba jest liczbą pierwszą. Jeśli tak, zwraca wartość prawda. Wykorzystuje ona algorytm przedstawiony w sekcji powyżej.

Funkcja wartośćBezwzględna() zwraca wartość bezwzględną z danej liczby.

Na początku sprawdzamy, czy różnica między liczbami wynosi 2. Jeżeli tak, to sprawdzamy, czy liczby są liczbami pierwszymi. W takim wypadku wiemy, że podane liczby są liczbami bliźniaczymi.

Liczby zaprzyjaźnione

Aby dwie liczby naturalne można było uznać za parę liczb zaprzyjaźnionych, suma dzielników właściwych pierwszej z nich musi być równa wartości drugiej liczby, natomiast suma dzielników właściwych drugiej liczby musi być równa wartości pierwszej liczby. Przykładem pary spełniającej ten warunek są liczby 220 i 284. Sprawdźmy:

  • dzielniki właściwe liczby 220:

    • 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 – ich suma wynosi 284;

  • dzielniki właściwe liczby 284:

    • 1, 2, 4, 71, 142 – ich suma wynosi 220.

Słownik

dzielnik
dzielnik

liczba, która dzieli bez reszty daną liczbę całkowitą

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

dzielniki danej liczby mniejsze od niej samej