Liczby pierwsze

Dobry wstęp

RHfnrg0BDnx7O1

Źródło: Contentplus.pl Sp. z o. o., licencja: CC BY-SA 3.0.

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

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ó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ą.

liczba ← wprowadź liczbę naturalną
czyPierwsza ← prawda

jeżeli liczba <= 1:
czyPierwsza ← fałsz
w przeciwnym razie:
i ← 2
dopóki i * i <= liczba:
jeżeli liczba mod i = 0:
czyPierwsza ← fałsz
przerwij pętlę
i ← i + 1

jeżeli czyPierwsza = prawda:
wypisz "Liczba jest liczbą pierwszą"
w przeciwnym razie:
wypisz "Liczba nie jest liczbą pierwszą"

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, \sqrt{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.

R11XS9PC2OFJS

Jeśli nie udało Ci się rozwiązać zadania skorzystaj z poniższego kodu.

Uwaga! W programie użyto klasy Scanner oraz obiektów klasy Skaner. Kond przed uruchomieniem na stronie należy zmodyfikować.

Ważne!

W programie użyto klasy Scanner oraz obiektów klasy Skaner. Kond przed uruchomieniem na stronie należy zmodyfikować.

Linia 1. import java kropka util kropka Scanner średnik. Linia 3. public class LiczbaPierwsza otwórz nawias klamrowy. Linia 4. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. int liczbaTest znak równości 0 średnik. Linia 6. boolean czyPierwsza znak równości true średnik. Linia 8. Scanner sc znak równości new Scanner otwórz nawias okrągły System kropka in zamknij nawias okrągły średnik. Linia 9. System kropka out kropka println otwórz nawias okrągły cudzysłów Podaj liczbę do sprawdzenia cudzysłów zamknij nawias okrągły średnik. Linia 10. liczbaTest znak równości sc kropka nextInt otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 12. if otwórz nawias okrągły liczbaTest znak równości znak równości 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. czyPierwsza znak równości false średnik. Linia 14. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 15. int i znak równości 2 średnik. Linia 16. while otwórz nawias okrągły i asterysk i znak równości znak równości liczbaTest zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. 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 18. czyPierwsza znak równości false średnik. Linia 19. break średnik. Linia 20. zamknij nawias klamrowy. Linia 21. i plus plus średnik. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 25. if otwórz nawias okrągły czyPierwsza znak równości znak równości false zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. System kropka out kropka println otwórz nawias okrągły cudzysłów Liczba cudzysłów plus liczbaTest plus cudzysłów nie jest liczbą pierwszą cudzysłów zamknij nawias okrągły średnik. Linia 27. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 28. System kropka out kropka println otwórz nawias okrągły cudzysłów Liczba cudzysłów plus liczbaTest plus cudzysłów jest liczbą pierwszą cudzysłów zamknij nawias okrągły średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy.

import java.util.Scanner;

public class LiczbaPierwsza {
    public static void main(String[] args) {        
        int liczbaTest = 0;
        boolean czyPierwsza = true;
    
        Scanner sc = new Scanner(System.in);
        System.out.println("Podaj liczbę do sprawdzenia");
        liczbaTest = sc.nextInt();
    
        if(liczbaTest == 1) {
            czyPierwsza = false;
        } else {
            int i = 2;
            while(i * i == liczbaTest) {
                if(liczbaTest % i == 0) {
                    czyPierwsza = false;
                    break; 
                }
                i++;
            }
        }
    
        if(czyPierwsza == false) {
            System.out.println("Liczba " + liczbaTest + " nie jest liczbą pierwszą");
        } else {
            System.out.println("Liczba " + liczbaTest + " jest liczbą pierwszą");
        }
    }

}

Już wiesz

Aby liczbę naturalną można było nazwać pierwszą, musi ona mieć tylko dwa dzielniki: 1 i samą siebie oraz jej wartość ma być większa od 1.

Poniżej zostało wypisanych kilka przykładowych liczb pierwszych:

2, 3, 5, 7, 11, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83

Słownik

dzielnik

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

dzielniki właściwe

dzielniki danej liczby mniejsze od niej samej

Na dobry początek

Przećwiczmy działanie programu

Liczby pierwsze

Dobry wstęp

Liczby pierwsze

Słownik