Zapis algorytmu w języku Python - I_P_W14_M03 Czy liczba jest liczbą pierwszą?

R78GBM2ZZ46P3

Już wiesz

Jakie własności musi posiadać liczbę, aby była liczbą pierwszą.
jak zapisać algorytm w pseudokodzie i języku Java, testujący czy dana liczba jest liczbą pierwszą.

Teraz czas, aby zapisać algorytm w postaci programu w języku Python.

Wersja I (wolniejsza, opiera się na definicji liczby pierwszej)

def czy_pierwsza(n):
    """
    Funkcja sprawdza, czy liczba n jest liczbą pierwszą.
    """
    if n < 2:
        return False  # liczby mniejsze od 2 nie są pierwsze

    # sprawdzamy wszystkie liczby od 2 do n-1
    for i in range(2, n):
        if n % i == 0:  # jeśli znajdziemy dzielnik
            return False
    return True  # brak dzielników, liczba jest pierwsza


# -----------------------------
# Program główny
# -----------------------------

liczba = int(input("Podaj liczbę: "))

if czy_pierwsza(liczba):
    print(f"Liczba {liczba} jest liczbą pierwszą.")
else:
    print(f"Liczba {liczba} nie jest liczbą pierwszą.")

Plik z programem do pobrania:

RB1PD8KK2H9KS

Przycisk do pobrania pliku TXT z programem.

Plik TXT o rozmiarze 674.00 B w języku polskim

Opis działania programu.

Sprawdzamy, czy liczba jest mniejsza od 2; wtedy na pewno nie jest pierwsza.
Szukamy dzielników wśród liczb naturalnych w zakresie od 2 do n‑1:

jeśli znajdziemy dzielnik, liczba nie jest pierwsza,
jeśli nie znajdziemy żadnego, to znaczy, że liczba jest pierwsza.

Ważne!

Ta metoda jest prostsza, ale wolniejsza dla dużych liczb, bo trzeba sprawdzić wszystkie możliwe dzielniki aż do n‑1.

Wersja II (szybsza, sprawdza dzielniki liczby w przedziale <2, sqrt(n)>)

Linia 1. from math import sqrt. Linia 2. def czy podkreślnik pierwsza otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 3. cudzysłów cudzysłów cudzysłów. Linia 4. Funkcja sprawdza przecinek czy liczba n jest liczbą pierwszą kropka. Linia 5. Liczba pierwsza to taka przecinek która ma dokładnie dwa dzielniki dwukropek 1 i samą siebie kropka. Linia 6. cudzysłów cudzysłów cudzysłów. Linia 7. kratka liczby mniejsze niż 2 nie są pierwsze. Linia 8. if n otwórz nawias ostrokątny 2 dwukropek. Linia 9. return False. Linia 11. kratka 2 jest pierwsza. Linia 12. if n znak równości znak równości 2 dwukropek. Linia 13. return True. Linia 15. kratka liczby parzyste większe od 2 nie są pierwsze. Linia 16. if n procent 2 znak równości znak równości 0 dwukropek. Linia 17. return False. Linia 19. kratka sprawdzamy dzielniki tylko do pierwiastka z n. Linia 20. kratka bo jeśli n znak równości a asterysk b przecinek to przynajmniej jeden z czynników ≤ √n. Linia 21. p znak równości int otwórz nawias okrągły sqrt otwórz nawias okrągły n zamknij nawias okrągły zamknij nawias okrągły. Linia 22. for i in range otwórz nawias okrągły 3 przecinek p plus 1 przecinek 2 zamknij nawias okrągły dwukropek kratka sprawdzamy tylko liczby nieparzyste. Linia 23. if n procent i znak równości znak równości 0 dwukropek. Linia 24. return False. Linia 26. return True. Linia 29. kratka minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus. Linia 30. kratka Program główny. Linia 31. kratka minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus minus. Linia 33. liczba znak równości int otwórz nawias okrągły input otwórz nawias okrągły cudzysłów Podaj liczbę dwukropek cudzysłów zamknij nawias okrągły zamknij nawias okrągły. Linia 35. if czy podkreślnik pierwsza otwórz nawias okrągły liczba zamknij nawias okrągły dwukropek. Linia 36. print otwórz nawias okrągły f cudzysłów Liczba otwórz nawias klamrowy liczba zamknij nawias klamrowy jest liczbą pierwszą kropka cudzysłów zamknij nawias okrągły. Linia 37. else dwukropek. Linia 38. print otwórz nawias okrągły f cudzysłów Liczba otwórz nawias klamrowy liczba zamknij nawias klamrowy nie jest liczbą pierwszą kropka cudzysłów zamknij nawias okrągły.

from math import sqrt
def czy_pierwsza(n):
    """
    Funkcja sprawdza, czy liczba n jest liczbą pierwszą.
    Liczba pierwsza to taka, która ma dokładnie dwa dzielniki: 1 i samą siebie.
    """
    # liczby mniejsze niż 2 nie są pierwsze
    if n < 2:
        return False
    
    # 2 jest pierwsza
    if n == 2:
        return True
    
    # liczby parzyste większe od 2 nie są pierwsze
    if n % 2 == 0:
        return False
    
    # sprawdzamy dzielniki tylko do pierwiastka z n
    # bo jeśli n = a * b, to przynajmniej jeden z czynników ≤ √n
    p = int(sqrt(n))
    for i in range(3, p + 1, 2):  # sprawdzamy tylko liczby nieparzyste
        if n % i == 0:
            return False
    
    return True


# -----------------------------
# Program główny
# -----------------------------

liczba = int(input("Podaj liczbę: "))

if czy_pierwsza(liczba):
    print(f"Liczba {liczba} jest liczbą pierwszą.")
else:
    print(f"Liczba {liczba} nie jest liczbą pierwszą.")

Plik z programem do pobrania:

R15FK721PV4CZ

Przycisk do pobrania pliku TXT z programem.

Plik TXT o rozmiarze 1.01 KB w języku polskim

Opis działania programu:

Sprawdzamy wyjątki: liczby mniejsze od 2 nie są pierwsze, a 2 jest jedyną parzystą liczbą pierwszą.
Odrzucamy parzyste – jeśli liczba > 2 i jest parzysta, od razu zwracamy False.
Sprawdzamy tylko do √n – przyspiesza działanie, bo nie musimy badać wszystkich dzielników.
Iterujemy tylko po nieparzystych (3, 5, 7, …).

Liczby i ich tajemnice

Dla zainteresowanych: Liczby bliźniacze