Sprawdzanie pierwszości liczby

To jeden z najważniejszych algorytmów występujących na maturze z informatyki, jako, iż wiele zadań opiera się na manipulacji liczbami pierwszymi naturalnymi.

Przedstawienie algorytmu w języku Python

def czy_pierwsza(n):
	if n < 2:
		return False
	i = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += 1
	return True

Wyjaśnienie algorytmu

Funkcja czy_pierwsza przyjmuje n jako liczbę naturalną, a zwraca werdykt, czy jest ona liczbą pierwszą. W pierwszym warunku upewniamy się, że liczba jest większa od jedynki, bowiem takie liczby nie mogą być pierwsze.

Występujący w pętli while kwadrat zmiennej iteracyjnej imituje działanie pierwiastka. Po co? Dlatego, że nie warto sprawdzać dzielników większych niż pierwiastek kwadratowy z n. Jest to zatem kwestia optymalizacji, a ponadto nasza implementacja nie wykorzystuje żadnej biblioteki.

Sprawdzamy zatem, czy liczby i = 4, 9, 16... dzielą liczbę n. Jeżeli tak - nie może być ona pierwsza.

Przykład

Sprawdźmy pierwszość liczby 31.

Nie znaleziono czynników, zatem liczba 31 jest pierwsza.